Anna Gál

Available identifiers

List of research outcomes

Publication	Date of Publication	Type
Diameter Versus Certificate Complexity of Boolean Functions	2023-08-08	Paper
Lower Bounds for (Non-Monotone) Comparator Circuits	2023-02-03	Paper
Tight bounds on sensitivity and block sensitivity of some classes of transitive functions	2023-02-01	Paper
Tight bounds on sensitivity and block sensitivity of some classes of transitive functions	2022-10-13	Paper
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity	2022-07-21	Paper
Cubic Formula Size Lower Bounds Based on Compositions with Majority	2022-07-18	Paper
Upper bounds on communication in terms of approximate rank	2022-03-21	Paper
Space-Efficient Approximations for Subset Sum	2019-12-06	Paper
Dual VP classes	2017-10-18	Paper
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates	2017-06-08	Paper
Batch Codes Through Dense Graphs Without Short Cycles	2017-04-28	Paper
A generalization of Spira's theorem and circuits with small segregators or separators	2016-11-18	Paper
A theorem on sensitivity and applications in private computation	2016-09-29	Paper
A simple function that requires exponential size read-once branching programs	2016-05-26	Paper
Optimal combinatorial batch codes based on block designs	2016-02-19	Paper
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length	2015-09-24	Paper
Dual VP Classes	2015-09-16	Paper
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates	2014-05-13	Paper
Hadamard tensors and lower bounds on multiparty communication complexity	2013-09-30	Paper
The size and depth of layered Boolean circuits	2013-04-04	Paper
On the correlation between parity and modular polynomials	2012-12-06	Paper
A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators	2012-06-15	Paper
Three query locally decodable codes with higher correctness require exponential length	2012-01-23	Paper
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence	2011-04-04	Paper
Lower bounds on the amount of randomness in private computation	2010-08-16	Paper
The Size and Depth of Layered Boolean Circuits	2010-04-27	Paper
A note on monotone complexity and the rank of matrices	2009-04-28	Paper
Incremental branching programs	2008-06-17	Paper
On the Correlation Between Parity and Modular Polynomials	2007-09-05	Paper
The cell probe complexity of succinct data structures	2007-07-16	Paper
Incremental Branching Programs	2007-05-02	Paper
Automata, Languages and Programming	2006-01-10	Paper
$\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation	2005-09-16	Paper
https://portal.mardi4nfdi.de/entity/Q4449186	2004-02-08	Paper
Communication Complexity of Simultaneous Messages	2004-01-08	Paper
A characterization of span program size and improved lower bounds for monotone span programs	2003-08-26	Paper
A Theorem on Sensitivity and Applications in Private Computation	2002-09-29	Paper
https://portal.mardi4nfdi.de/entity/Q4542561	2002-08-01	Paper
On arithmetic branching programs	2000-11-22	Paper
Superpolynomial lower bounds for monotone span programs	2000-05-14	Paper
https://portal.mardi4nfdi.de/entity/Q4258572	1999-09-13	Paper
https://portal.mardi4nfdi.de/entity/Q4252753	1999-08-31	Paper
https://portal.mardi4nfdi.de/entity/Q4228516	1999-07-05	Paper
Lower bounds for monotone span programs	1997-09-07	Paper
Boolean complexity classes vs. their arithmetic analogs	1996-10-07	Paper
Lower bounds for the complexity of reliable Boolean circuits with noisy gates	1995-03-05	Paper

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Anna Gál