Anna Gál, Ridwan Syed:

"Upper bounds on communication in terms of approximate rank",

Proceedings of CSR 2021, to appear.

See also ECCC Report TR19-006, 2019.

Siddhesh Chaubal, Anna Gál:

"Tight bounds on sensitivity and block sensitivity of some classes of
transitive functions"

Proceedings of LATIN 2020, pp. 323 - 335.

See also ECCC Report TR20-134, 2020.

Anna Gál, Robert Robere:

"Lower bounds for (non-monotone) comparator circuits",

Proceedings of ITCS, pp. 58:1-58:13, 2020.

See also ECCC Report TR19-128, 2019.

Anna Gál, Avishay Tal, Adrian Trejo Nunez:

"Cubic formula size lower bounds based on compositions with majority",

Proceedings of ITCS, pp. 35:1-35:13, 2019.

See also ECCC Report TR18-160, 2018.

Siddhesh Chaubal, Anna Gál:

"New constructions with quadratic separation between sensitivity and block sensitivity"

Proceedings of FSTTCS pp. 13:1 - 13:16, 2018.

See also ECCC Report TR18-205, 2018.

E. Allender, A. Gál, I. Mertz:

"Dual VP classes",

* Computational Complexity, * Vol. 26(3), pp. 583-625,
2017.

Preliminary version in Proceedings of MFCS (Mathematical Foundations of Computer Science), pp. 14-25, 2015.

See also ECCC Report TR14-122, 2014.

A. Gál, J. T. Jang, N. Limaye, M. Mahajan, K. Sreenivasaiah:

"Space-Efficient Approximations for Subset Sum",

* ACM Transactions on Computation Theory, * 8(4): 16, 2016.

See also ECCC Report TR21:180, 2014.

A. Gál, Jing-Tang Jang:

"A generalization of Spira's theorem and circuits with small
segregators or separators",

* Information and Computation, * 251(C) pp. 252-262, 2016.

Preliminary version in Proceedings of SOFSEM 2012, pp. 264-276.

See also ECCC Report TR13-93, 2013.

N. Silberstein, A. Gál:

"Optimal Combinatorial Batch Codes based on Block Designs",

* Designs, Codes and Cryptography, * 78(2), pp. 409-424, 2016.

A. S. Rawat, Z. Song, A. Dimakis, A. Gál:

"Batch Codes through Dense Graphs without Short Cycles",

* IEEE Transactions on Information Theory, * 62(4)
pp. 1592-1604, 2016.

Preliminary version in Proceedings of ISIT (IEEE International Symposium on Information Theory), pp. 1477-1481, 2015.

See also ECCC Report TR21:127, 2014.

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.

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.

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.

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