Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny:
"Certificate Games",
Proceedings of ITCS 2022, to appear.
See also ECCC Report TR22-143, 2022.
Siddhesh Chaubal, Anna Gál:
"Diameter Versus Certificate Complexity of Boolean Functions",
Proceedings of MFCS 2021, pp. 31: 1-31 : 22, (2021)
See also ECCC Report TR22-059, 2022.
Anna Gál, Ridwan Syed:
"Upper bounds on communication in terms of approximate rank",
Proceedings of CSR 2021, pp. 116 - 130, (2021)
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.)