| Publication | Date of Publication | Type |
|---|
The approximate degree of DNF and CNF formulas
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing | 2023-12-08 | Paper |
An optimal separation of randomized and Quantum query complexity
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
scientific article; zbMATH DE number 7716601 (Why is no real title available?)
(available as arXiv preprint) | 2023-07-25 | Paper |
An Optimal Separation of Randomized and Quantum Query Complexity
SIAM Journal on Computing | 2023-04-28 | Paper |
Inner product and set disjointness: beyond logarithmically many parties
ACM Transactions on Computation Theory | 2022-03-07 | Paper |
The hardest halfspace
Computational Complexity | 2021-09-10 | Paper |
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$
SIAM Journal on Computing | 2021-09-10 | Paper |
Algorithmic Polynomials
SIAM Journal on Computing | 2020-12-04 | Paper |
Near-optimal lower bounds on the threshold degree and sign-rank of \(\mathrm{AC}^0\)
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Optimal Interactive Coding for Insertions, Deletions, and Substitutions
IEEE Transactions on Information Theory | 2020-01-28 | Paper |
Algorithmic polynomials
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
On multiparty communication with large versus unbounded error
Theory of Computing | 2019-01-31 | Paper |
The power of asymmetry in constant-depth circuits
SIAM Journal on Computing | 2018-12-19 | Paper |
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
SIAM Journal on Computing | 2018-11-07 | Paper |
Compressing interactive communication under product distributions
SIAM Journal on Computing | 2018-04-24 | Paper |
The multiparty communication complexity of set disjointness
SIAM Journal on Computing | 2016-09-02 | Paper |
Communication lower bounds using directional derivatives
Journal of the ACM | 2015-08-14 | Paper |
Breaking the Minsky-Papert barrier for constant-depth circuits
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
Combinatorica | 2015-03-03 | Paper |
Communication complexity theory: thirty-five years of set disjointness
Mathematical Foundations of Computer Science 2014 | 2014-10-14 | Paper |
Making polynomials robust to noise
Theory of Computing | 2014-10-06 | Paper |
Approximating the AND-OR tree
Theory of Computing | 2014-10-06 | Paper |
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Communication lower bounds using directional derivatives
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2014-08-07 | Paper |
The Intersection of Two Halfspaces Has High Threshold Degree
2009 50th Annual IEEE Symposium on Foundations of Computer Science | 2014-07-25 | Paper |
Strong direct product theorems for quantum communication and query complexity
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
The multiparty communication complexity of set disjointness
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
Making polynomials robust to noise
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
The intersection of two halfspaces has high threshold degree
SIAM Journal on Computing | 2014-04-11 | Paper |
A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length
Mathematical Notes | 2013-09-18 | Paper |
Strong direct product theorems for quantum communication and query complexity
SIAM Journal on Computing | 2013-02-04 | Paper |
The communication complexity of gap Hamming distance
Theory of Computing | 2012-09-27 | Paper |
The unbounded-error communication complexity of symmetric functions
Combinatorica | 2012-04-26 | Paper |
The pattern matrix method
SIAM Journal on Computing | 2012-03-15 | Paper |
| scientific article; zbMATH DE number 5953454 (Why is no real title available?) | 2011-10-05 | Paper |
A separation of NP and conp in multiparty communication complexity
Theory of Computing | 2011-05-24 | Paper |
Approximate inclusion-exclusion for arbitrary symmetric functions
Computational Complexity | 2011-02-18 | Paper |
Lower bounds for agnostic learning via approximate rank
Computational Complexity | 2011-02-18 | Paper |
Communication complexity under product and nonproduct distributions
Computational Complexity | 2011-02-07 | Paper |
The Sign-Rank of AC$^0$
SIAM Journal on Computing | 2010-11-04 | Paper |
Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length
Russian Mathematical Surveys | 2010-04-08 | Paper |
Powering requires threshold depth 3
Information Processing Letters | 2010-01-29 | Paper |
Separating AC\(^0\) from depth-2 majority circuits
SIAM Journal on Computing | 2010-01-06 | Paper |
| scientific article; zbMATH DE number 5605137 (Why is no real title available?) | 2009-09-19 | Paper |
Unconditional lower bounds for learning intersections of halfspaces
Machine Learning | 2009-03-31 | Paper |
Cryptographic hardness for learning intersections of halfspaces
Journal of Computer and System Sciences | 2009-01-09 | Paper |
| scientific article; zbMATH DE number 5485463 (Why is no real title available?) | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5485519 (Why is no real title available?) | 2009-01-05 | Paper |
Halfspace matrices
Computational Complexity | 2008-08-20 | Paper |
A Lower Bound for Agnostically Learning Disjunctions
Learning Theory | 2008-01-03 | Paper |
Improved Lower Bounds for Learning Intersections of Halfspaces
Learning Theory | 2007-09-14 | Paper |
