Travelled to:1 × Portugal
1 × The Netherlands
5 × USA
Collaborated with:A.Rosén J.Ford P.B.Miltersen ∅ K.A.Hansen M.Koucký P.Pudlák E.Viola L.Babai J.Kollár L.Rónyai T.Szabó A.Wigderson
Talks about:bound (6) lower (4) program (3) comput (3) span (3) monoton (2) complex (2) privat (2) superpolynomi (1) multiparti (1)
Person: Anna Gál
DBLP: G=aacute=l:Anna
Contributed to:
2012
200520032003199919981996Wrote 7 papers:
- STOC-2012-GalHKPV #bound
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates (AG, KAH, MK, PP, EV), pp. 479–494.
- ICALP-2005-FordG #bound #communication #complexity #multi
- Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity (JF, AG), pp. 1163–1175.
- ICALP-2003-GalM #complexity #data type
- The Cell Probe Complexity of Succinct Data Structures (AG, PBM), pp. 332–344.
- STOC-2003-GalR #bound
- Lower bounds on the amount of randomness in private computation (AG, AR), pp. 659–666.
- STOC-1999-GalR #theorem
- A Theorem on Sensitivity and Applications in Private Computation (AG, AR), pp. 348–357.
- STOC-1998-Gal #bound #source code
- A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs (AG), pp. 429–437.
- STOC-1996-BabaiGKRSW #bound #graph #source code
- Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs (LB, AG, JK, LR, TS, AW), pp. 603–611.