Anna Gál

Affiliations:

University of Texas at Austin, USA

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.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Bibliography

2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2023

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

[BibT_eX]

[DOI]

Siddhesh Chaubal

Anna Gál

Theor. Comput. Sci., February, 2023

2022

Diameter versus Certificate Complexity of Boolean Functions.

[BibT_eX]

[DOI]

Siddhesh Chaubal

Anna Gál

Electron. Colloquium Comput. Complex., 2022

Certificate games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2021

2019

Upper Bounds on Communication in terms of Approximate Rank.

[BibT_eX]

[DOI]

Anna Gál

Ridwan Syed

Electron. Colloquium Comput. Complex., 2019

Lower Bounds for (Non-monotone) Comparator Circuits.

[BibT_eX]

[DOI]

Anna Gál

Robert Robere

Electron. Colloquium Comput. Complex., 2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).

[BibT_eX]

[DOI]

Anna Gál

Rahul Santhanam

Till Tantau

Dagstuhl Reports, 2019

2018

Cubic Formula Size Lower Bounds Based on Compositions with Majority.

[BibT_eX]

[DOI]

Anna Gál

Avishay Tal

Adrian Trejo Nuñez

Electron. Colloquium Comput. Complex., 2018

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity.

[BibT_eX]

[DOI]

Siddhesh Chaubal

Anna Gál

Electron. Colloquium Comput. Complex., 2018

2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2017

Dual VP Classes.

[BibT_eX]

[DOI]

Eric Allender

Anna Gál

Ian Mertz

Comput. Complex., 2017

2016

Optimal combinatorial batch codes based on block designs.

[BibT_eX]

[DOI]

Natalia Silberstein

Anna Gál

Des. Codes Cryptogr., 2016

2014

Space-Efficient Approximations for Subset Sum.

[BibT_eX]

[DOI]

Karteek Sreenivasaiah

Electron. Colloquium Comput. Complex., 2014

Batch Codes through Dense Graphs without Short Cycles.

[BibT_eX]

[DOI]

Alexandros G. Dimakis

Anna Gál

Ankit Singh Rawat

Zhao Song

Electron. Colloquium Comput. Complex., 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

2013

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

[BibT_eX]

[DOI]

Anna Gál

Jing-Tang Jang

Electron. Colloquium Comput. Complex., 2013

Hadamard tensors and lower bounds on multiparty communication complexity.

[BibT_eX]

[DOI]

Jeff Ford

Anna Gál

Comput. Complex., 2013

2012

On the Correlation Between Parity and Modular Polynomials.

[BibT_eX]

[DOI]

Anna Gál

Vladimir Trifonov

Theory Comput. Syst., 2012

Correctness and Corruption of Locally Decodable Codes.

[BibT_eX]

[DOI]

Mahdi Cheraghchi

Anna Gál

Andrew Mills

Electron. Colloquium Comput. Complex., 2012

2011

The size and depth of layered Boolean circuits.

[BibT_eX]

[DOI]

Anna Gál

Jing-Tang Jang

Inf. Process. Lett., 2011

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

[BibT_eX]

[DOI]

Anna Gál

Andrew Mills

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Anna Gál

Kristoffer Arnsfelt Hansen

Michal Koucký

Pavel Pudlák

Emanuele Viola

Electron. Colloquium Comput. Complex., 2011

2010

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

[BibT_eX]

[DOI]

Anna Gál

Parikshit Gopalan

SIAM J. Comput., 2010

2009

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

[BibT_eX]

[DOI]

Anna Gál

Theor. Comput. Sci., 2009

2007

The cell probe complexity of succinct data structures.

[BibT_eX]

[DOI]

Anna Gál

Peter Bro Miltersen

Theor. Comput. Sci., 2007

2006

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

[BibT_eX]

[DOI]

Anna Gál

Comput. Complex., 2006

2005

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

[BibT_eX]

[DOI]

Anna Gál

Adi Rosén

SIAM J. Comput., 2005

Incremental branching programs

[BibT_eX]

[DOI]

Anna Gál

Michal Koucký

Pierre McKenzie

Electron. Colloquium Comput. Complex., 2005

2003

Communication Complexity of Simultaneous Messages.

[BibT_eX]

[DOI]

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].

[BibT_eX]

[DOI]

Anna Gál

Pavel Pudlák

Inf. Process. Lett., 2003

A note on monotone complexity and the rank of matrices.

[BibT_eX]

[DOI]

Anna Gál

Pavel Pudlák

Inf. Process. Lett., 2003

Lower bounds on the amount of randomness in private computation.

[BibT_eX]

[DOI]

Anna Gál

Adi Rosén

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

2002

A Theorem on Sensitivity and Applications in Private Computation.

[BibT_eX]

[DOI]

Anna Gál

Adi Rosén

SIAM J. Comput., 2002

2001

A characterization of span program size and improved lower bounds for monotone span programs.

[BibT_eX]

[DOI]

Anna Gál

Comput. Complex., 2001

1999

On Arithmetic Branching Programs.

[BibT_eX]

[DOI]

Amos Beimel

Anna Gál

J. Comput. Syst. Sci., 1999

Superpolynomial Lower Bounds for Monotone Span Programs.

[BibT_eX]

[DOI]

László Babai

Anna Gál

Avi Wigderson

Comb., 1999

Computing from Partial Solutions.

[BibT_eX]

[DOI]

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

1997

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

[BibT_eX]

[DOI]

Anna Gál

Inf. Process. Lett., 1997

Lower Bounds for Monotone Span Programs.

[BibT_eX]

[DOI]

Amos Beimel

Anna Gál

Mike Paterson

Comput. Complex., 1997

1996

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

[BibT_eX]

[DOI]

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

1995

Boolean Complexity Classes vs. Their Arithmetic Analogs

[BibT_eX]

[DOI]

Anna Gál

Avi Wigderson

Electron. Colloquium Comput. Complex., 1995

Fault Tolerant Circuits and Probabilistically Checkable Proofs.

[BibT_eX]

[DOI]

Anna Gál

Mario Szegedy

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

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

[BibT_eX]

[DOI]

Anna Gál

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

Anna Gál

Timeline

Legend:

Links

Online presence:

On csauthors.net:

Bibliography

Loading...