Anna Gál

91 papers A* 10A 7B 6Misc 2Journal 59Unranked 7
YearRankTypeTitle / Venue / Authors
2026 J jnl
Nearly Tight Bounds on the Block Number of Boolean Functions in Terms of Sensitivity.
Electron. Colloquium Comput. Complex.
Sourav Chakraborty, Anna Gál
2026 A conf
Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length.
ITCS
Anna Gál, Gillat Kol, Raghuvansh R. Saxena, Huacheng Yu
2026 J jnl
Separations above TFNP from Sherali-Adams Lower Bounds.
CoRR
Anna Gál, Noah Fleming, Deniz Imrek, Christophe Marciot
2026 J jnl
Separations above TFNP from Sherali-Adams Lower Bounds.
Electron. Colloquium Comput. Complex.
Noah Fleming, Anna Gál, Christophe Marciot, Deniz Imrek
2025 J jnl
Optimal White-Box Adversarial Streaming Lower Bounds for Approximating LIS Length.
Electron. Colloquium Comput. Complex.
Anna Gál, Gillat Kol, Raghuvansh Saxena, Huacheng Yu
2024 J jnl
Upper Bounds on Communication in Terms of Approximate Rank.
Theory Comput. Syst.
Anna Gál, Ridwan Syed
2023 A conf
Certificate Games.
ITCS
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
2023 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, Manaswi Paraashar
2023 J jnl
Tight bounds on sensitivity and block sensitivity of some classes of transitive functions.
Theor. Comput. Sci.
Siddhesh Chaubal, Anna Gál
2022 J jnl
Certificate games.
CoRR
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
2022 J jnl
Certificate games.
Electron. Colloquium Comput. Complex.
Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, Anupa Sunny
2022 J jnl
Diameter versus Certificate Complexity of Boolean Functions.
Electron. Colloquium Comput. Complex.
Siddhesh Chaubal, Anna Gál
2021 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).
Dagstuhl Reports
Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau
2021 B conf
Diameter Versus Certificate Complexity of Boolean Functions.
MFCS
Siddhesh Chaubal, Anna Gál
2021 Misc conf
Upper Bounds on Communication in Terms of Approximate Rank.
CSR
Anna Gál, Ridwan Syed
2020 A conf
Lower Bounds for (Non-Monotone) Comparator Circuits.
ITCS
Anna Gál, Robert Robere
2020 B conf
Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions.
LATIN
Siddhesh Chaubal, Anna Gál
2020 J jnl
Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions.
Electron. Colloquium Comput. Complex.
Siddhesh Chaubal, Anna Gál
2019 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).
Dagstuhl Reports
Anna Gál, Rahul Santhanam, Till Tantau
2019 A conf
Cubic Formula Size Lower Bounds Based on Compositions with Majority.
ITCS
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
2019 J jnl
Lower Bounds for (Non-monotone) Comparator Circuits.
Electron. Colloquium Comput. Complex.
Anna Gál, Robert Robere
2019 J jnl
Upper Bounds on Communication in terms of Approximate Rank.
Electron. Colloquium Comput. Complex.
Anna Gál, Ridwan Syed
2018 J jnl
Cubic Formula Size Lower Bounds Based on Compositions with Majority.
Electron. Colloquium Comput. Complex.
Anna Gál, Avishay Tal, Adrian Trejo Nuñez
2018 — conf
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity.
FSTTCS
Siddhesh Chaubal, Anna Gál
2018 J jnl
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity.
Electron. Colloquium Comput. Complex.
Siddhesh Chaubal, Anna Gál
2017 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).
Dagstuhl Reports
Anna Gál, Michal Koucký, Oded Regev, Till Tantau
2017 J jnl
Dual VP Classes.
Comput. Complex.
Eric Allender, Anna Gál, Ian Mertz
2016 J jnl
A generalization of Spira's theorem and circuits with small segregators or separators.
Inf. Comput.
Anna Gál, Jing-Tang Jang
2016 J jnl
Batch Codes Through Dense Graphs Without Short Cycles.
IEEE Trans. Inf. Theory
Ankit Singh Rawat, Zhao Song, Alexandros G. Dimakis, Anna Gál
2016 J jnl
Optimal combinatorial batch codes based on block designs.
Des. Codes Cryptogr.
Natalia Silberstein, Anna Gál
2016 J jnl
Space-Efficient Approximations for Subset Sum.
ACM Trans. Comput. Theory
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2015 B conf
Batch codes through dense graphs without short cycles.
ISIT
Ankit Singh Rawat, Zhao Song, Alexandros G. Dimakis, Anna Gál
2015 — conf
Dual VP Classes.
MFCS (2)
Eric Allender, Anna Gál, Ian Mertz
2014 J jnl
Batch Codes through Dense Graphs without Short Cycles.
CoRR
Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song
2014 J jnl
Batch Codes through Dense Graphs without Short Cycles.
Electron. Colloquium Comput. Complex.
Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song
2014 J jnl
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).
Dagstuhl Reports
Anna Gál, Michal Koucký, Oded Regev, Rüdiger Reischuk
2014 J jnl
Dual VP Classes.
Electron. Colloquium Comput. Complex.
Eric Allender, Anna Gál, Ian Mertz
2014 J jnl
Space-Efficient Approximations for Subset Sum.
Electron. Colloquium Comput. Complex.
Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah
2013 J jnl
A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators.
Electron. Colloquium Comput. Complex.
Anna Gál, Jing-Tang Jang
2013 J jnl
Hadamard tensors and lower bounds on multiparty communication complexity.
Comput. Complex.
Jeff Ford, Anna Gál
2013 J jnl
Optimal Combinatorial Batch Codes based on Block Designs.
CoRR
Natalia Silberstein, Anna Gál
2013 J jnl
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates.
IEEE Trans. Inf. Theory
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
2012 B conf
A Generalization of Spira's Theorem and Circuits with Small Segregators or Separators.
SOFSEM
Anna Gál, Jing-Tang Jang
2012 J jnl
Correctness and Corruption of Locally Decodable Codes.
Electron. Colloquium Comput. Complex.
Mahdi Cheraghchi, Anna Gál, Andrew Mills
2012 J jnl
On the Correlation Between Parity and Modular Polynomials.
Theory Comput. Syst.
Anna Gál, Vladimir Trifonov
2012 J jnl
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length.
ACM Trans. Comput. Theory
Anna Gál, Andrew Mills
2012 A* conf
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
STOC
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
2011 J jnl
The size and depth of layered Boolean circuits.
Inf. Process. Lett.
Anna Gál, Jing-Tang Jang
2011 A conf
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length.
STACS
Anna Gál, Andrew Mills
2011 J jnl
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length.
Electron. Colloquium Comput. Complex.
Anna Gál, Andrew Mills
2011 J jnl
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates.
Electron. Colloquium Comput. Complex.
Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, Emanuele Viola
2010 J jnl
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
SIAM J. Comput.
Anna Gál, Parikshit Gopalan
2010 B conf
The Size and Depth of Layered Boolean Circuits.
LATIN
Anna Gál, Jing-Tang Jang
2009 J jnl
Preface: Special Issue of ICALP 2006 - dedicated to the memory of Ingo Wegener.
Theor. Comput. Sci.
Anna Gál
2008 J jnl
Incremental Branching Programs.
Theory Comput. Syst.
Anna Gál, Michal Koucký, Pierre McKenzie
2007 A* conf
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
FOCS
Anna Gál, Parikshit Gopalan
2007 J jnl
The cell probe complexity of succinct data structures.
Theor. Comput. Sci.
Anna Gál, Peter Bro Miltersen
2006 — conf
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
Complexity of Boolean Functions
Jeff Ford, Anna Gál
2006 Misc conf
Incremental Branching Programs.
CSR
Anna Gál, Michal Koucký, Pierre McKenzie
2006 — conf
Incremental branching programs.
Complexity of Boolean Functions
Anna Gál, Pierre McKenzie, Michal Koucký
2006 B conf
On the Correlation Between Parity and Modular Polynomials.
MFCS
Anna Gál, Vladimir Trifonov
2006 J jnl
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Comput. Complex.
Anna Gál
2006 J jnl
Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword.
Comput. Complex.
Anna Gál
2006 — conf
The Cell Probe Complexity of Succinct Data Structures.
Complexity of Boolean Functions
Anna Gál, Peter Bro Miltersen
2005 A* conf
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity.
ICALP
Jeff Ford, Anna Gál
2005 J jnl
Incremental branching programs
Electron. Colloquium Comput. Complex.
Anna Gál, Michal Koucký, Pierre McKenzie
2005 J jnl
Omega(log n) Lower Bounds on the Amount of Randomness in 2-Private Computation.
SIAM J. Comput.
Anna Gál, Adi Rosén
2003 J jnl
A note on monotone complexity and the rank of matrices.
Inf. Process. Lett.
Anna Gál, Pavel Pudlák
2003 J jnl
Communication Complexity of Simultaneous Messages.
SIAM J. Comput.
László Babai, Anna Gál, Peter G. Kimmel, Satyanarayana V. Lokam
2003 J jnl
Erratum to: "A note on monotone complexity and the rank of matrices": [Information Processing Letters 87 (2003) 321-326].
Inf. Process. Lett.
Anna Gál, Pavel Pudlák
2003 A* conf
Lower bounds on the amount of randomness in private computation.
STOC
Anna Gál, Adi Rosén
2003 A* conf
The Cell Probe Complexity of Succinct Data Structures.
ICALP
Anna Gál, Peter Bro Miltersen
2002 J jnl
A Theorem on Sensitivity and Applications in Private Computation.
SIAM J. Comput.
Anna Gál, Adi Rosén
2001 J jnl
A characterization of span program size and improved lower bounds for monotone span programs.
Comput. Complex.
Anna Gál
1999 A* conf
A Theorem on Sensitivity and Applications in Private Computation.
STOC
Anna Gál, Adi Rosén
1999 A conf
Computing from Partial Solutions.
CCC
Anna Gál, Shai Halevi, Richard J. Lipton, Erez Petrank
1999 J jnl
On Arithmetic Branching Programs.
J. Comput. Syst. Sci.
Amos Beimel, Anna Gál
1999 J jnl
Superpolynomial Lower Bounds for Monotone Span Programs.
Comb.
László Babai, Anna Gál, Avi Wigderson
1998 A* conf
A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs.
STOC
Anna Gál
1998 A conf
On Arithmetic Branching Programs.
CCC
Amos Beimel, Anna Gál
1997 J jnl
A Simple Function that Requires Exponential Size Read-Once Branching Programs.
Inf. Process. Lett.
Anna Gál
1997 J jnl
Lower Bounds for Monotone Span Programs.
Comput. Complex.
Amos Beimel, Anna Gál, Mike Paterson
1996 J jnl
Boolean complexity classes vs. their arithmetic analogs.
Random Struct. Algorithms
Anna Gál, Avi Wigderson
1996 A* conf
Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs.
STOC
László Babai, Anna Gál, János Kollár, Lajos Rónyai, Tibor Szabó, Avi Wigderson
1995 J jnl
Boolean Complexity Classes vs. Their Arithmetic Analogs
Electron. Colloquium Comput. Complex.
Anna Gál, Avi Wigderson
1995 — conf
Fault Tolerant Circuits and Probabilistically Checkable Proofs.
SCT
Anna Gál, Mario Szegedy
1995 J jnl
Lower Bounds for Monotone Span Programs
Electron. Colloquium Comput. Complex.
Amos Beimel, Anna Gál, Mike Paterson
1995 A* conf
Lower Bounds for Monotone Span Programs.
FOCS
Amos Beimel, Anna Gál, Mike Paterson
1995 — conf
Semi-Unbounded Fan-In Circuits: Boolean vs. Arithmetic.
SCT
Anna Gál
1994 J jnl
Lower bounds for the complexity of reliable Boolean circuits with noisy gates.
IEEE Trans. Inf. Theory
Péter Gács, Anna Gál
1991 A* conf
Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates
FOCS
Anna Gál