 | 2008 |
|---|
| 36 |       | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental Branching Programs.
Theory Comput. Syst. 43(2): 159-184 (2008) |
| 2007 |
|---|
| 35 | | Anna Gál,
Parikshit Gopalan:
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
FOCS 2007: 294-304 |
| 34 | | Anna Gál,
Peter Bro Miltersen:
The cell probe complexity of succinct data structures.
Theor. Comput. Sci. 379(3): 405-417 (2007) |
| 2006 |
|---|
| 33 | | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental Branching Programs.
CSR 2006: 178-190 |
| 32 | | Jeff Ford,
Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
Complexity of Boolean Functions 2006 |
| 31 | | Anna Gál,
Pierre McKenzie,
Michal Koucký:
Incremental branching programs.
Complexity of Boolean Functions 2006 |
| 30 | | Anna Gál,
Peter Bro Miltersen:
The Cell Probe Complexity of Succinct Data Structures.
Complexity of Boolean Functions 2006 |
| 29 | | Anna Gál,
Vladimir Trifonov:
On the Correlation Between Parity and Modular Polynomials.
MFCS 2006: 387-398 |
| 28 | | Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Computational Complexity 15(2): 93 (2006) |
| 27 | | Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Computational Complexity 15(4): 297 (2006) |
| 2005 |
|---|
| 26 | | Jeff Ford,
Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
ICALP 2005: 1163-1175 |
| 25 | | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental branching programs
Electronic Colloquium on Computational Complexity (ECCC)(136): (2005) |
| 24 | | Anna Gál,
Adi Rosén:
Omega(log n) Lower Bounds on the Amount of Randomness in 2-Private Computation.
SIAM J. Comput. 34(4): 946-959 (2005) |
| 2003 |
|---|
| 23 | | Anna Gál,
Peter Bro Miltersen:
The Cell Probe Complexity of Succinct Data Structures.
ICALP 2003: 332-344 |
| 22 | | Anna Gál,
Adi Rosén:
Lower bounds on the amount of randomness in private computation.
STOC 2003: 659-666 |
| 21 | | Anna Gál,
Pavel Pudlák:
A note on monotone complexity and the rank of matrices.
Inf. Process. Lett. 87(6): 321-326 (2003) |
| 20 | | Anna Gál,
Pavel Pudlák:
Erratum to: "A note on monotone complexity and the rank of matrices": [Information Processing Letters 87 (2003) 321-326].
Inf. Process. Lett. 88(5): 257 (2003) |
| 19 | | László Babai,
Anna Gál,
Peter G. Kimmel,
Satyanarayana V. Lokam:
Communication Complexity of Simultaneous Messages.
SIAM J. Comput. 33(1): 137-166 (2003) |
| 2002 |
|---|
| 18 | | Anna Gál,
Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation.
SIAM J. Comput. 31(5): 1424-1437 (2002) |
| 2001 |
|---|
| 17 | | Anna Gál:
A characterization of span program size and improved lower bounds for monotone span programs.
Computational Complexity 10(4): 277-296 (2001) |
| 1999 |
|---|
| 16 | | Anna Gál,
Shai Halevi,
Richard J. Lipton,
Erez Petrank:
Computing from Partial Solutions.
IEEE Conference on Computational Complexity 1999: 34-45 |
| 15 | | Anna Gál,
Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation.
STOC 1999: 348-357 |
| 14 | | László Babai,
Anna Gál,
Avi Wigderson:
Superpolynomial Lower Bounds for Monotone Span Programs.
Combinatorica 19(3): 301-319 (1999) |
| 13 |  | Amos Beimel,
Anna Gál:
On Arithmetic Branching Programs.
J. Comput. Syst. Sci. 59(2): 195-220 (1999) |
| 1998 |
|---|
| 12 | | Amos Beimel,
Anna Gál:
On Arithmetic Branching Programs.
IEEE Conference on Computational Complexity 1998: 68-80 |
| 11 | | Anna Gál:
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.
STOC 1998: 429-437 |
| 1997 |
|---|
| 10 | | Amos Beimel,
Anna Gál,
Mike Paterson:
Lower Bounds for Monotone Span Programs.
Computational Complexity 6(1): 29-45 (1997) |
| 9 | | Anna Gál:
A Simple Function that Requires Exponential Size Read-Once Branching Programs.
Inf. Process. Lett. 62(1): 13-16 (1997) |
| 1996 |
|---|
| 8 | | László Babai,
Anna Gál,
János Kollár,
Lajos Rónyai,
Tibor Szabó,
Avi Wigderson:
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.
STOC 1996: 603-611 |
| 7 | | Anna Gál,
Avi Wigderson:
Boolean complexity classes vs. their arithmetic analogs.
Random Struct. Algorithms 9(1-2): 99-111 (1996) |
| 1995 |
|---|
| 6 | | Amos Beimel,
Anna Gál,
Mike Paterson:
Lower Bounds for Monotone Span Programs.
FOCS 1995: 674-681 |
| 5 | | Anna Gál,
Mario Szegedy:
Fault Tolerant Circuits and Probabilistically Checkable Proofs.
Structure in Complexity Theory Conference 1995: 65-73 |
| 4 | | Anna Gál:
Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic.
Structure in Complexity Theory Conference 1995: 82-87 |
| 3 | | Amos Beimel,
Anna Gál,
Mike Paterson:
Lower Bounds for Monotone Span Programs
Electronic Colloquium on Computational Complexity (ECCC) 2(1): (1995) |
| 2 | | Anna Gál,
Avi Wigderson:
Boolean Complexity Classes vs. Their Arithmetic Analogs
Electronic Colloquium on Computational Complexity (ECCC) 2(49): (1995) |
| 1991 |
|---|
| 1 | | Anna Gál:
Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates
FOCS 1991: 594-601 |
