The following pages link to Anna Gál (Q247136):
Displaying 49 items.
- A simple function that requires exponential size read-once branching programs (Q287023) (← links)
- A generalization of Spira's theorem and circuits with small segregators or separators (Q342721) (← links)
- Hadamard tensors and lower bounds on multiparty communication complexity (Q371197) (← links)
- Lower bounds for monotone span programs (Q677989) (← links)
- On the correlation between parity and modular polynomials (Q692898) (← links)
- Incremental branching programs (Q929291) (← links)
- A note on monotone complexity and the rank of matrices (Q1014450) (← links)
- (Q1405736) (redirect page) (← links)
- A characterization of span program size and improved lower bounds for monotone span programs (Q1405737) (← links)
- The size and depth of layered Boolean circuits (Q1944075) (← links)
- On arithmetic branching programs (Q1961372) (← links)
- Superpolynomial lower bounds for monotone span programs (Q1977413) (← links)
- Upper bounds on communication in terms of approximate rank (Q2117081) (← links)
- The cell probe complexity of succinct data structures (Q2373728) (← links)
- Dual VP classes (Q2410687) (← links)
- A theorem on sensitivity and applications in private computation (Q2819565) (← links)
- A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators (Q2891374) (← links)
- Dual VP Classes (Q2946373) (← links)
- Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length (Q2947559) (← links)
- Batch Codes Through Dense Graphs Without Short Cycles (Q2976882) (← links)
- Three query locally decodable codes with higher correctness require exponential length (Q3113729) (← links)
- A Theorem on Sensitivity and Applications in Private Computation (Q3149875) (← links)
- Incremental Branching Programs (Q3434693) (← links)
- The Size and Depth of Layered Boolean Circuits (Q3557034) (← links)
- Lower bounds on the amount of randomness in private computation (Q3581281) (← links)
- (Q4228516) (← links)
- (Q4252753) (← links)
- (Q4258572) (← links)
- Lower bounds for the complexity of reliable Boolean circuits with noisy gates (Q4308807) (← links)
- Communication Complexity of Simultaneous Messages (Q4441903) (← links)
- (Q4449186) (← links)
- (Q4542561) (← links)
- Boolean complexity classes vs. their arithmetic analogs (Q4894604) (← links)
- Space-Efficient Approximations for Subset Sum (Q4973861) (← links)
- Cubic Formula Size Lower Bounds Based on Compositions with Majority (Q5090412) (← links)
- New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity (Q5090948) (← links)
- $\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation (Q5317183) (← links)
- Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates (Q5346309) (← links)
- Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence (Q5390602) (← links)
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates (Q5415496) (← links)
- Automata, Languages and Programming (Q5716862) (← links)
- On the Correlation Between Parity and Modular Polynomials (Q5756672) (← links)
- Lower Bounds for (Non-Monotone) Comparator Circuits (Q5875761) (← links)
- Tight bounds on sensitivity and block sensitivity of some classes of transitive functions (Q5918507) (← links)
- Tight bounds on sensitivity and block sensitivity of some classes of transitive functions (Q5925611) (← links)
- Optimal combinatorial batch codes based on block designs (Q5963364) (← links)
- Diameter Versus Certificate Complexity of Boolean Functions (Q6168445) (← links)
- Certificate games (Q6610295) (← links)
- Upper bounds on communication in terms of approximate rank (Q6635689) (← links)
