The copyrights for journal and conference proceedings papers belong to the respective publishers. All papers may be downloaded for personal or research purposes only.

Selected Publications of Anna Gál

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",
IEEE Transactions on Information Theory , Vol. 59(10): pp.6611-6627, 2013.
Preliminary version in Proceedings of STOC 2012, pp. 479-494.
See also ECCC Report TR11-150, 2011.

A. Gál, Jing-Tang Jang:
"A generalization of Spira's theorem and circuits with small segregators or separators",
In Proceedings of SOFSEM 2012, pp. 264-276.
See also ECCC Report TR13-93, 2013.

M. Cheraghchi, A. Gál, A. Mills
"Correctness and corruption of locally decodable codes"
ECCC Report TR12-172, 2012.

A. Gál, A. Mills
"Three query locally decodable codes with higher correctness require exponential length",
ACM Transactions on Computation Theory , Vol. 3(2): 5, 2012.
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",
Computational Complexity , Vol. 22(3) pp. 595-622, 2013
Preliminary version in
ICALP 2005, pp. 1163 - 1175.

A. Gál, V. Trifonov:
"On the correlation between parity and modular polynomials",
Theory of Computing Systems , Vol. 50(3), pp. 516-536 (2012).
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 - panni@cs.utexas.edu