Anna Gál

Publication Activity (10 Years)

Years Active: 1991-2023
Publications (10 Years): 25

Top Topics

Related Problems

Boolean Functions

Top Venues

Electron. Colloquium Comput. Complex.

Dagstuhl Reports

Publications

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