Publication | Date of Publication | Type |
---|
The approximate degree of DNF and CNF formulas | 2023-12-08 | Paper |
An optimal separation of randomized and Quantum query complexity | 2023-11-14 | Paper |
https://portal.mardi4nfdi.de/entity/Q6176153 | 2023-07-25 | Paper |
An Optimal Separation of Randomized and Quantum Query Complexity | 2023-04-28 | Paper |
Inner Product and Set Disjointness | 2022-03-07 | Paper |
The hardest halfspace | 2021-09-10 | Paper |
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$ | 2021-09-10 | Paper |
Algorithmic Polynomials | 2020-12-04 | Paper |
Near-optimal lower bounds on the threshold degree and sign-rank of AC 0 | 2020-01-30 | Paper |
Optimal Interactive Coding for Insertions, Deletions, and Substitutions | 2020-01-28 | Paper |
Algorithmic polynomials | 2019-08-22 | Paper |
https://portal.mardi4nfdi.de/entity/Q4612487 | 2019-01-31 | Paper |
The Power of Asymmetry in Constant-Depth Circuits | 2018-12-19 | Paper |
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits | 2018-11-07 | Paper |
Compressing Interactive Communication Under Product Distributions | 2018-04-24 | Paper |
The Multiparty Communication Complexity of Set Disjointness | 2016-09-02 | Paper |
Communication Lower Bounds Using Directional Derivatives | 2015-08-14 | Paper |
Breaking the minsky-papert barrier for constant-depth circuits | 2015-06-26 | Paper |
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials | 2015-03-03 | Paper |
Communication Complexity Theory: Thirty-Five Years of Set Disjointness | 2014-10-14 | Paper |
https://portal.mardi4nfdi.de/entity/Q3191588 | 2014-10-06 | Paper |
https://portal.mardi4nfdi.de/entity/Q3191590 | 2014-10-06 | Paper |
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials | 2014-08-13 | Paper |
Communication lower bounds using directional derivatives | 2014-08-07 | Paper |
The Intersection of Two Halfspaces Has High Threshold Degree | 2014-07-25 | Paper |
Strong Direct Product Theorems for Quantum Communication and Query Complexity | 2014-06-05 | Paper |
The multiparty communication complexity of set disjointness | 2014-05-13 | Paper |
Making polynomials robust to noise | 2014-05-13 | Paper |
The Intersection of Two Halfspaces Has High Threshold Degree | 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 | 2013-09-18 | Paper |
Strong Direct Product Theorems for Quantum Communication and Query Complexity | 2013-02-04 | Paper |
https://portal.mardi4nfdi.de/entity/Q2913808 | 2012-09-27 | Paper |
The unbounded-error communication complexity of symmetric functions | 2012-04-26 | Paper |
The Pattern Matrix Method | 2012-03-15 | Paper |
https://portal.mardi4nfdi.de/entity/Q3171603 | 2011-10-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q3002823 | 2011-05-24 | Paper |
Approximate inclusion-exclusion for arbitrary symmetric functions | 2011-02-18 | Paper |
Lower bounds for agnostic learning via approximate rank | 2011-02-18 | Paper |
Communication complexity under product and nonproduct distributions | 2011-02-07 | Paper |
The Sign-Rank of AC$^0$ | 2010-11-04 | Paper |
Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length | 2010-04-08 | Paper |
Powering requires threshold depth 3 | 2010-01-29 | Paper |
Separating ${AC}^0$ from Depth-2 Majority Circuits | 2010-01-06 | Paper |
https://portal.mardi4nfdi.de/entity/Q3396635 | 2009-09-19 | Paper |
Unconditional lower bounds for learning intersections of halfspaces | 2009-03-31 | Paper |
Cryptographic hardness for learning intersections of halfspaces | 2009-01-09 | Paper |
https://portal.mardi4nfdi.de/entity/Q3549625 | 2009-01-05 | Paper |
https://portal.mardi4nfdi.de/entity/Q3549688 | 2009-01-05 | Paper |
Halfspace matrices | 2008-08-20 | Paper |
A Lower Bound for Agnostically Learning Disjunctions | 2008-01-03 | Paper |
Improved Lower Bounds for Learning Intersections of Halfspaces | 2007-09-14 | Paper |