Anna Gál

According to our database, Anna Gál authored at least 46 papers between 1991 and 2023.

Collaborative distances:

• Dijkstra number of two.
• Erdős number of two.

2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar

Dagstuhl Reports, March, 2023

Certificate Games.

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau

Dagstuhl Reports, 2021

Diameter Versus Certificate Complexity of Boolean Functions.

Siddhesh Chaubal, Anna Gál

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

Upper Bounds on Communication in Terms of Approximate Rank.

Anna Gál, Ridwan Syed

Proceedings of the Computer Science - Theory and Applications, 2021

2020

Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions.

Siddhesh Chaubal, Anna Gál

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

Lower Bounds for (Non-Monotone) Comparator Circuits.

Anna Gál, Robert Robere

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).

Anna Gál, Rahul Santhanam, Till Tantau

Dagstuhl Reports, 2019

Cubic Formula Size Lower Bounds Based on Compositions with Majority.

Anna Gál, Avishay Tal, Adrian Trejo Nuñez

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity.

Siddhesh Chaubal, Anna Gál

Proceedings of the 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2018

2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

Anna Gál, Michal Koucký, Oded Regev, Till Tantau

Dagstuhl Reports, 2017

2016

Optimal combinatorial batch codes based on block designs.

Natalia Silberstein, Anna Gál

Des. Codes Cryptogr., 2016

2015

Dual VP Classes.

Eric Allender, Anna Gál, Ian Mertz

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

Batch codes through dense graphs without short cycles.

Ankit Singh Rawat, Zhao Song, Alexandros G. Dimakis, Anna Gál

Proceedings of the IEEE International Symposium on Information Theory, 2015

2014

Space-Efficient Approximations for Subset Sum.

Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk

Dagstuhl Reports, 2014

2012

Correctness and Corruption of Locally Decodable Codes.

Mahdi Cheraghchi, Anna Gál, Andrew Mills

Electron. Colloquium Comput. Complex., 2012

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.

Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators.

Anna Gál, Jing-Tang Jang

Proceedings of the SOFSEM 2012: Theory and Practice of Computer Science, 2012

2011

Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length.

Anna Gál, Andrew Mills

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

The Size and Depth of Layered Boolean Circuits.

Anna Gál, Jing-Tang Jang

Proceedings of the LATIN 2010: Theoretical Informatics, 2010

2009

Preface: Special Issue of ICALP 2006 - dedicated to the memory of Ingo Wegener.

Anna Gál

Theor. Comput. Sci., 2009

2007

Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.

Anna Gál, Parikshit Gopalan

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

2006

Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.

Anna Gál

Comput. Complex., 2006

On the Correlation Between Parity and Modular Polynomials.

Anna Gál, Vladimir Trifonov

Proceedings of the Mathematical Foundations of Computer Science 2006, 2006

The Cell Probe Complexity of Succinct Data Structures.

Anna Gál, Peter Bro Miltersen

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.

Jeff Ford, Anna Gál

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

Incremental Branching Programs.

Anna Gál, Michal Koucký, Pierre McKenzie

Proceedings of the Computer Science, 2006

2005

Omega(log n) Lower Bounds on the Amount of Randomness in 2-Private Computation.

Anna Gál, Adi Rosén

SIAM J. Comput., 2005

2003

Communication Complexity of Simultaneous Messages.

László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam

SIAM J. Comput., 2003

Erratum to: "A note on monotone complexity and the rank of matrices": [Information Processing Letters 87 (2003) 321-326].

Anna Gál, Pavel Pudlák

Inf. Process. Lett., 2003

A note on monotone complexity and the rank of matrices.

Anna Gál, Pavel Pudlák

Inf. Process. Lett., 2003

Lower bounds on the amount of randomness in private computation.

Anna Gál, Adi Rosén

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

1999

Superpolynomial Lower Bounds for Monotone Span Programs.

László Babai, Anna Gál, Avi Wigderson

Comb., 1999

A Theorem on Sensitivity and Applications in Private Computation.

Anna Gál, Adi Rosén

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Computing from Partial Solutions.

Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.

Anna Gál

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

On Arithmetic Branching Programs.

Amos Beimel, Anna Gál

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

A Simple Function that Requires Exponential Size Read-Once Branching Programs.

Anna Gál

Inf. Process. Lett., 1997

1996

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.

László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995

Boolean Complexity Classes vs. Their Arithmetic Analogs

Anna Gál, Avi Wigderson

Electron. Colloquium Comput. Complex., 1995

Lower Bounds for Monotone Span Programs.

Amos Beimel, Anna Gál, Mike Paterson

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

Fault Tolerant Circuits and Probabilistically Checkable Proofs.

Anna Gál, Mario Szegedy

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic.

Anna Gál

Proceedings of the Tenth Annual Structure in Complexity Theory Conference, 1995

1994

Lower bounds for the complexity of reliable Boolean circuits with noisy gates.

Péter Gács, Anna Gál

IEEE Trans. Inf. Theory, 1994

1991

Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates

Anna Gál

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991