Notice: Unexpected clearActionName after getActionName already called in /var/www/html/w/includes/context/RequestContext.php on line 333
Alexander A. Sherstov - MaRDI portal

Alexander A. Sherstov

From MaRDI portal
(Redirected from Person:368234)
Person:623503

Available identifiers

zbMath Open sherstov.alexander-aMaRDI QIDQ623503

List of research outcomes





PublicationDate of PublicationType
The approximate degree of DNF and CNF formulas2023-12-08Paper
An optimal separation of randomized and Quantum query complexity2023-11-14Paper
https://portal.mardi4nfdi.de/entity/Q61761532023-07-25Paper
An Optimal Separation of Randomized and Quantum Query Complexity2023-04-28Paper
Inner Product and Set Disjointness2022-03-07Paper
The hardest halfspace2021-09-10Paper
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$2021-09-10Paper
Algorithmic Polynomials2020-12-04Paper
Near-optimal lower bounds on the threshold degree and sign-rank of AC 02020-01-30Paper
Optimal Interactive Coding for Insertions, Deletions, and Substitutions2020-01-28Paper
Algorithmic polynomials2019-08-22Paper
https://portal.mardi4nfdi.de/entity/Q46124872019-01-31Paper
The Power of Asymmetry in Constant-Depth Circuits2018-12-19Paper
Breaking the Minsky--Papert Barrier for Constant-Depth Circuits2018-11-07Paper
Compressing Interactive Communication Under Product Distributions2018-04-24Paper
The Multiparty Communication Complexity of Set Disjointness2016-09-02Paper
Communication Lower Bounds Using Directional Derivatives2015-08-14Paper
Breaking the minsky-papert barrier for constant-depth circuits2015-06-26Paper
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials2015-03-03Paper
Communication Complexity Theory: Thirty-Five Years of Set Disjointness2014-10-14Paper
https://portal.mardi4nfdi.de/entity/Q31915882014-10-06Paper
https://portal.mardi4nfdi.de/entity/Q31915902014-10-06Paper
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials2014-08-13Paper
Communication lower bounds using directional derivatives2014-08-07Paper
The Intersection of Two Halfspaces Has High Threshold Degree2014-07-25Paper
Strong Direct Product Theorems for Quantum Communication and Query Complexity2014-06-05Paper
The multiparty communication complexity of set disjointness2014-05-13Paper
Making polynomials robust to noise2014-05-13Paper
The Intersection of Two Halfspaces Has High Threshold Degree2014-04-11Paper
A small decrease in the degree of a polynomial with a given sign function can exponentially increase its weight and length2013-09-18Paper
Strong Direct Product Theorems for Quantum Communication and Query Complexity2013-02-04Paper
https://portal.mardi4nfdi.de/entity/Q29138082012-09-27Paper
The unbounded-error communication complexity of symmetric functions2012-04-26Paper
The Pattern Matrix Method2012-03-15Paper
https://portal.mardi4nfdi.de/entity/Q31716032011-10-05Paper
https://portal.mardi4nfdi.de/entity/Q30028232011-05-24Paper
Approximate inclusion-exclusion for arbitrary symmetric functions2011-02-18Paper
Lower bounds for agnostic learning via approximate rank2011-02-18Paper
Communication complexity under product and nonproduct distributions2011-02-07Paper
The Sign-Rank of AC$^0$2010-11-04Paper
Reducing by 1 the degree of a polynomial with fixed sign function can increase exponentially its weight and length2010-04-08Paper
Powering requires threshold depth 32010-01-29Paper
Separating ${AC}^0$ from Depth-2 Majority Circuits2010-01-06Paper
https://portal.mardi4nfdi.de/entity/Q33966352009-09-19Paper
Unconditional lower bounds for learning intersections of halfspaces2009-03-31Paper
Cryptographic hardness for learning intersections of halfspaces2009-01-09Paper
https://portal.mardi4nfdi.de/entity/Q35496252009-01-05Paper
https://portal.mardi4nfdi.de/entity/Q35496882009-01-05Paper
Halfspace matrices2008-08-20Paper
A Lower Bound for Agnostically Learning Disjunctions2008-01-03Paper
Improved Lower Bounds for Learning Intersections of Halfspaces2007-09-14Paper

Research outcomes over time

This page was built for person: Alexander A. Sherstov