| Publication | Date of Publication | Type |
|---|
Upper bounds on communication in terms of approximate rank
Theory of Computing Systems | 2024-11-12 | Paper |
| Certificate games | 2024-09-25 | Paper |
| 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
Theoretical Computer Science | 2023-02-01 | Paper |
Tight bounds on sensitivity and block sensitivity of some classes of transitive functions
LATIN 2020: Theoretical Informatics | 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
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Dual VP classes
Computational Complexity | 2017-10-18 | Paper |
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
IEEE Transactions on Information Theory | 2017-06-08 | Paper |
Batch Codes Through Dense Graphs Without Short Cycles
IEEE Transactions on Information Theory | 2017-04-28 | Paper |
A generalization of Spira's theorem and circuits with small segregators or separators
Information and Computation | 2016-11-18 | Paper |
A theorem on sensitivity and applications in private computation
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
A simple function that requires exponential size read-once branching programs
Information Processing Letters | 2016-05-26 | Paper |
Optimal combinatorial batch codes based on block designs
Designs, Codes and Cryptography | 2016-02-19 | Paper |
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Dual VP classes
Mathematical Foundations of Computer Science 2015 | 2015-09-16 | Paper |
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Hadamard tensors and lower bounds on multiparty communication complexity
Computational Complexity | 2013-09-30 | Paper |
The size and depth of layered Boolean circuits
Information Processing Letters | 2013-04-04 | Paper |
On the correlation between parity and modular polynomials
Theory of Computing Systems | 2012-12-06 | Paper |
A generalization of Spira's theorem and circuits with small segregators or separators
SOFSEM 2012: Theory and Practice of Computer Science | 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
SIAM Journal on Computing | 2011-04-04 | Paper |
Lower bounds on the amount of randomness in private computation
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
The size and depth of layered Boolean circuits
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
A note on monotone complexity and the rank of matrices
Information Processing Letters | 2009-04-28 | Paper |
Incremental branching programs
Theory of Computing Systems | 2008-06-17 | Paper |
On the Correlation Between Parity and Modular Polynomials
Lecture Notes in Computer Science | 2007-09-05 | Paper |
The cell probe complexity of succinct data structures
Theoretical Computer Science | 2007-07-16 | Paper |
Incremental Branching Programs
Computer Science – Theory and Applications | 2007-05-02 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
$\Omega(\log n)$ Lower Bounds on the Amount of Randomness in 2-Private Computation
SIAM Journal on Computing | 2005-09-16 | Paper |
| scientific article; zbMATH DE number 2038721 (Why is no real title available?) | 2004-02-08 | Paper |
Communication Complexity of Simultaneous Messages
SIAM Journal on Computing | 2004-01-08 | Paper |
A characterization of span program size and improved lower bounds for monotone span programs
Computational Complexity | 2003-08-26 | Paper |
A Theorem on Sensitivity and Applications in Private Computation
SIAM Journal on Computing | 2002-09-29 | Paper |
| scientific article; zbMATH DE number 1775428 (Why is no real title available?) | 2002-08-01 | Paper |
On arithmetic branching programs
Journal of Computer and System Sciences | 2000-11-22 | Paper |
Superpolynomial lower bounds for monotone span programs
Combinatorica | 2000-05-14 | Paper |
| scientific article; zbMATH DE number 1335881 (Why is no real title available?) | 1999-09-13 | Paper |
| scientific article; zbMATH DE number 1306900 (Why is no real title available?) | 1999-08-31 | Paper |
| scientific article; zbMATH DE number 1256780 (Why is no real title available?) | 1999-07-05 | Paper |
Lower bounds for monotone span programs
Computational Complexity | 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
IEEE Transactions on Information Theory | 1995-03-05 | Paper |
