A. Gál, K. A. Hansen, M. Koucky, P. Pudlak and E. Viola:
"Tight bounds on computing error-correcting codes by bounded-depth
circuits with arbitrary gates",
ECCC Report TR11-150, 2011.
A. Gál, Jing-Tang Jang:
"A generalization of Spira's theorem and circuits with small
segregators or separators",
To appear in Proceedings of SOFSEM 2012.
A. Gál, A. Mills
"Three query locally decodable codes with higher correctness
require exponential length",
To appear in ACM Transactions on Computation Theory , 2011
Preliminary version in
Proceedings of STACS 2011, pp. 673 - 684 (2011).
See also ECCC Report TR11-030, 2011.
J. Ford and A. Gál:
"Hadamard tensors and lower bounds on multiparty communication complexity",
To appear in Computational Complexity , 2011
Preliminary version in
ICALP 2005, pp. 1163 - 1175.
A. Gál, V. Trifonov:
"On the correlation between parity and modular polynomials",
To appear in Theory of Computing Systems , 2011.
Published online on journal's website, May 11, 2011.
Preliminary version in
Proceedings of MFCS 2006, LNCS 4162, pp. 387-398.
A. Gál, Jing-Tang Jang:
"The size and depth of layered Boolean circuits",
Information Processing Letters
Vol. 111, No. 5, pp. 213-217, 2011.
Preliminary version in
Proceedings of LATIN 2010, pp. 372-383.
A. Gál, P. Gopalan:
"Lower bounds on streaming algorithms for approximating the length of
the longest increasing subsequence",
SIAM Journal on Computing
Vol. 39, No. 8, pp. 3463-3479, 2010.
Preliminary version in
Proceedings of FOCS 2007, pp. 294-304.
A. Gál, M. Koucky and P. McKenzie:
"Incremental branching programs",
Theory of Computing Systems ,
Volume 43, No. 2, pp. 159-184., 2008.
Special Issue of Selected papers from CSR.
Preliminary version in
Proceedings of CSR 2006
(International Computer Science Symposium in Russia), LNCS 3967,
pp. 178-190.
A. Gál and Peter Bro Miltersen:
"The cell probe complexity of succinct data structures",
Theoretical Computer Science , vol 379, pp. 405 - 417, 2007.
Preliminary version in
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.)