Alexander A. Sherstov

Available identifiers

zbMath Open sherstov.alexander-aMaRDI QIDQ623503

List of research outcomes

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

Research outcomes over time

Doctoral students

No records found.

Known relations from the MaRDI Knowledge Graph

Property	Value
MaRDI profile type	MaRDI person profile
instance of	human

This page was built for person: Alexander A. Sherstov