A. Gál, P. Gopalan:
"Lower bounds on streaming algorithms for approximating the length of
the longest increasing subsequence",
Proceedings of FOCS 2007, pp. 294-304.
A. Gál, V. Trifonov:
"On the correlation between parity and modular polynomials",
Proceedings of MFCS 2006, LNCS 4162, pp. 387-398.
A. Gál, M. Koucky and P. McKenzie:
"Incremental branching programs",
Proceedings of CSR 2006
(International Computer Science Symposium in Russia), LNCS 3967,
pp. 178-190.
J. Ford and A. Gál:
"Hadamard tensors and lower bounds on multiparty communication complexity",
ICALP 2005, pp. 1163 - 1175.
A. Gál and Peter Bro Miltersen:
"The cell probe complexity of succinct data structures",
ICALP 2003, pp. 332-344. (Received EATCS best paper award
at Track A of ICALP 2003.)
A. Gál and A. Rosén:
"Omega(log N) lower bounds on the amount of randomness in 2-private computation",
SIAM Journal on Computing,
Vol. 34, No. 4, 2005, pp. 946-959.
Preliminary version in
Proc. of 35th ACM Symposium on Theory
of Computing, 2003, pp. 659-666.
A. Gál and P. Pudlák:
"A note on monotone complexity and the rank of matrices",
Information Processing Letters
, Vol. 87, No. 6, 2003, pp. 321-326.
L. Babai, A. Gál, P. Kimmel, S. V. Lokam:
"Simultaneous messages vs. communication",
SIAM Journal on Computing, Vol. 33, No. 1, 2003, pp. 137-166.
A. Gál and A. Rosén:
"A theorem on sensitivity and applications
in private computation",
SIAM Journal on Computing,
Vol. 31, No. 5, 2002, pp. 1424-1437.
Preliminary version in
Proc. of 31st ACM Symposium on Theory
of Computing, 1999, pp. 348-357.
A. Gál:
"A characterization of span program size and
improved lower bounds for monotone span programs",
Computational Complexity, Vol. 10, No. 4, 2001, pp. 277-296.
Preliminary version in
Proc. of 30th ACM Symposium on Theory
of Computing, 1998, pp. 429-437.
A. Gál, S. Halevi, R. Lipton, E. Petrank:
``Computing from
partial solutions'',
Proc. of 14th IEEE
Conference on Computational Complexity, 1999, pp. 34-45.
A. Beimel and A. Gál:
"On Arithmetic Branching Programs",
Journal of Computer Systems
Sciences , 59, 1999, pp. 195-220.
Preliminary version in
Proc. of 13th IEEE
Conference on Computational Complexity, 1998, pp. 68-80.
L. Babai, A. Gál, A. Wigderson:
"Superpolynomial lower bounds for monotone span programs",
Combinatorica 19 (3), 1999, pp. 301-319.
L. Babai, A. Gál, J. Kollár, L. Rónyai, T. Szabó,
A. Wigderson:
``Extremal bipartite graphs and superpolynomial lower bounds
for monotone span programs'',
Proc. of 28th ACM Symposium on the Theory of Computing,
1996, pp. 603-611.
A. Beimel, A. Gál, M. Paterson:
``Lower bounds for monotone
span programs'',
Computational Complexity, 6, 1996/1997, pp. 29-45.
Preliminary version in Proc. of 36th IEEE Symposium on
Foundations of Computer Science, 1995, pp. 674-681.
A. Gál:
"A simple function that requires exponential size read
once
branching programs",
Information Processing Letters 62, 1997, pp. 13-16.
A. Gál, A. Wigderson:
``Boolean vs. arithmetic complexity
classes: randomized reductions'',
Random Structures and
Algorithms, Vol. 9, Nos. 1 and 2, 1996, pp. 99-111.
A. Gál:
``Semi-unbounded fan-in circuits: Boolean vs.
arithmetic'',
Proc. of 10th IEEE
Structure in Complexity Theory Conference, 1995, pp. 82-87.
A. Gál, M. Szegedy:
``Fault tolerant circuits and
probabilistically checkable proofs'',
Proc. of 10th IEEE
Structure in Complexity Theory Conference, 1995, pp. 65-73.
P. Gács, A. Gál:
``Lower bounds for the complexity
of reliable Boolean circuits with noisy gates'',
IEEE Transactions on Information Theory,
Vol. 40, No. 2, 1994, pp. 579-583.
A. Gál:
``Lower bounds for the complexity of reliable Boolean
circuits with noisy gates'',
Proc. of 32nd IEEE Symposium on
Foundations of Computer Science, 1991, pp. 594-601.
(Received Machtey Award for best student paper at FOCS 1991.)
Anna Gál:
Combinatorial Methods in Boolean Function Complexity,
Ph.D. Thesis, Department of Computer Science, University of Chicago, 1995.
(Published on
ECCC - Electronic Colloquium on Computational Complexity,
under Books/Theses.)