2008 |
36 | EE | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental Branching Programs.
Theory Comput. Syst. 43(2): 159-184 (2008) |
2007 |
35 | EE | Anna Gál,
Parikshit Gopalan:
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
FOCS 2007: 294-304 |
34 | EE | Anna Gál,
Peter Bro Miltersen:
The cell probe complexity of succinct data structures.
Theor. Comput. Sci. 379(3): 405-417 (2007) |
2006 |
33 | EE | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental Branching Programs.
CSR 2006: 178-190 |
32 | EE | Jeff Ford,
Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
Complexity of Boolean Functions 2006 |
31 | EE | Anna Gál,
Pierre McKenzie,
Michal Koucký:
Incremental branching programs.
Complexity of Boolean Functions 2006 |
30 | EE | Anna Gál,
Peter Bro Miltersen:
The Cell Probe Complexity of Succinct Data Structures.
Complexity of Boolean Functions 2006 |
29 | EE | Anna Gál,
Vladimir Trifonov:
On the Correlation Between Parity and Modular Polynomials.
MFCS 2006: 387-398 |
28 | EE | Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Computational Complexity 15(2): 93 (2006) |
27 | EE | Anna Gál:
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Computational Complexity 15(4): 297 (2006) |
2005 |
26 | EE | Jeff Ford,
Anna Gál:
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
ICALP 2005: 1163-1175 |
25 | EE | Anna Gál,
Michal Koucký,
Pierre McKenzie:
Incremental branching programs
Electronic Colloquium on Computational Complexity (ECCC)(136): (2005) |
24 | EE | 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 | EE | Anna Gál,
Peter Bro Miltersen:
The Cell Probe Complexity of Succinct Data Structures.
ICALP 2003: 332-344 |
22 | EE | Anna Gál,
Adi Rosén:
Lower bounds on the amount of randomness in private computation.
STOC 2003: 659-666 |
21 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | 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 | EE | Anna Gál,
Shai Halevi,
Richard J. Lipton,
Erez Petrank:
Computing from Partial Solutions.
IEEE Conference on Computational Complexity 1999: 34-45 |
15 | EE | Anna Gál,
Adi Rosén:
A Theorem on Sensitivity and Applications in Private Computation.
STOC 1999: 348-357 |
14 | EE | 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 | EE | Amos Beimel,
Anna Gál:
On Arithmetic Branching Programs.
IEEE Conference on Computational Complexity 1998: 68-80 |
11 | EE | 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 | EE | Anna Gál:
A Simple Function that Requires Exponential Size Read-Once Branching Programs.
Inf. Process. Lett. 62(1): 13-16 (1997) |
1996 |
8 | EE | 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 | EE | Amos Beimel,
Anna Gál,
Mike Paterson:
Lower Bounds for Monotone Span Programs
Electronic Colloquium on Computational Complexity (ECCC) 2(1): (1995) |
2 | EE | 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 |