Alexander A. Sherstov

ORCID

Publication Activity (10 Years)

Years Active: 2002-2023
Publications (10 Years): 38

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

SIAM J. Comput.

STOC

Publications

Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
An Optimal Separation of Randomized and Quantum Query Complexity. SIAM J. Comput. 52 (2) (2023)
Alexander A. Sherstov
The Approximate Degree of DNF and CNF Formulas. Electron. Colloquium Comput. Complex. (2022)
Alexander A. Sherstov
The Approximate Degree of DNF and CNF Formulas. CoRR (2022)
Alexander A. Sherstov
The approximate degree of DNF and CNF formulas. STOC (2022)
Alexander A. Sherstov
The hardest halfspace. Comput. Complex. 30 (2) (2021)
Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum communication complexity of distribution testing. Quantum Inf. Comput. 21 (15&16) (2021)
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
An optimal separation of randomized and Quantum query complexity. STOC (2021)
Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
Quantum Communication Complexity of Distribution Testing. CoRR (2020)
Alexander A. Sherstov
Algorithmic Polynomials. SIAM J. Comput. 49 (6) (2020)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory 12 (4) (2020)
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
An Optimal Separation of Randomized and Quantum Query Complexity. Electron. Colloquium Comput. Complex. 27 (2020)
Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
An Optimal Separation of Randomized and Quantum Query Complexity. CoRR (2020)
Alexander A. Sherstov, Pei Wu
. STOC (2019)
Alexander A. Sherstov, Justin Thaler
Vanishing-Error Approximate Degree and QMA Complexity. CoRR (2019)
Alexander A. Sherstov, Pei Wu
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. IEEE Trans. Inf. Theory 65 (10) (2019)
Alexander A. Sherstov
The Hardest Halfspace. CoRR (2019)
Alexander A. Sherstov, Pei Wu
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander A. Sherstov, Justin Thaler
Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander A. Sherstov, Pei Wu
Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. CoRR (2019)
Alexander A. Sherstov
The hardest halfspace. Electron. Colloquium Comput. Complex. 26 (2019)
Alexander A. Sherstov
Algorithmic Polynomials. CoRR (2018)
Alexander A. Sherstov
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. SIAM J. Comput. 47 (5) (2018)
Alexander A. Sherstov
On Multiparty Communication with Large versus Unbounded Error. Theory Comput. 14 (1) (2018)
Alexander A. Sherstov
Compressing Interactive Communication Under Product Distributions. SIAM J. Comput. 47 (2) (2018)
Alexander A. Sherstov
Algorithmic polynomials. STOC (2018)
Alexander A. Sherstov
The Power of Asymmetry in Constant-Depth Circuits. SIAM J. Comput. 47 (6) (2018)
Alexander A. Sherstov
Algorithmic polynomials. Electron. Colloquium Comput. Complex. 25 (2018)
Alexander A. Sherstov, Pei Wu
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Electron. Colloquium Comput. Complex. 24 (2017)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. 24 (2017)
Vladimir V. Podolskii, Alexander A. Sherstov
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR (2017)
Alexander A. Sherstov, Pei Wu
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. FOCS (2017)
Alexander A. Sherstov
On multiparty communication with large versus unbounded error. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander A. Sherstov
Compressing Interactive Communication under Product Distributions. FOCS (2016)
Alexander A. Sherstov
The Multiparty Communication Complexity of Set Disjointness. SIAM J. Comput. 45 (4) (2016)
Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov
Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. FOCS (2016)
Alexander A. Sherstov
Compressing interactive communication under product distributions. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander A. Sherstov
The Power of Asymmetry in Constant-Depth Circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Alexander A. Sherstov
The Power of Asymmetry in Constant-Depth Circuits. FOCS (2015)
Alexander A. Sherstov
Communication Complexity Theory: Thirty-Five Years of Set Disjointness. MFCS (1) (2014)
Alexander A. Sherstov
Communication Lower Bounds Using Directional Derivatives. J. ACM 61 (6) (2014)
Alexander A. Sherstov
Breaking the minsky-papert barrier for constant-depth circuits. STOC (2014)
Alexander A. Sherstov
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Alexander A. Sherstov
Approximating the AND-OR Tree. Theory Comput. 9 (2013)
Alexander A. Sherstov
Communication Lower Bounds Using Directional Derivatives. Electron. Colloquium Comput. Complex. 20 (2013)
Alexander A. Sherstov
Making Polynomials Robust to Noise. Theory Comput. 9 (2013)
Alexander A. Sherstov
Communication lower bounds using directional derivatives. STOC (2013)
Alexander A. Sherstov
Approximating the AND-OR Tree. Electron. Colloquium Comput. Complex. 20 (2013)
Alexander A. Sherstov
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Comb. 33 (1) (2013)
Alexander A. Sherstov
The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput. 42 (6) (2013)
Alexander A. Sherstov
The Communication Complexity of Gap Hamming Distance. Theory Comput. 8 (1) (2012)
Alexander A. Sherstov
Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. 41 (5) (2012)
Alexander A. Sherstov
Making Polynomials Robust to Noise. Electron. Colloquium Comput. Complex. 19 (2012)
Alexander A. Sherstov
The multiparty communication complexity of set disjointness. STOC (2012)
Alexander A. Sherstov
Making polynomials robust to noise. STOC (2012)
Alexander A. Sherstov
The Pattern Matrix Method. SIAM J. Comput. 40 (6) (2011)
Alexander A. Sherstov
The Multiparty Communication Complexity of Set Disjointness. Electron. Colloquium Comput. Complex. 18 (2011)
Alexander A. Sherstov
Strong direct product theorems for quantum communication and query complexity. STOC (2011)
Alexander A. Sherstov
Strong Direct Product Theorems for Quantum Communication and Query Complexity. Electron. Colloquium Comput. Complex. 18 (2011)
Alexander A. Sherstov
The Communication Complexity of Gap Hamming Distance. Electron. Colloquium Comput. Complex. 18 (2011)
Alexander A. Sherstov
The unbounded-error communication complexity of symmetric functions. Comb. 31 (5) (2011)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. 6 (1) (2010)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. 17 (2010)
Alexander A. Sherstov
Strong direct product theorems for quantum communication and query complexity CoRR (2010)
Alexander A. Sherstov
On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. 10 (5&6) (2010)
Dmitry Gavinsky, Alexander A. Sherstov
A Separation of NP and coNP in Multiparty Communication Complexity CoRR (2010)
Alexander A. Sherstov
Communication Complexity Under Product and Nonproduct Distributions. Comput. Complex. 19 (1) (2010)
Alexander A. Sherstov
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Electron. Colloquium Comput. Complex. 17 (2010)
Adam R. Klivans, Alexander A. Sherstov
Lower Bounds for Agnostic Learning via Approximate Rank. Comput. Complex. 19 (4) (2010)
Alexander A. Razborov, Alexander A. Sherstov
. SIAM J. Comput. 39 (5) (2010)
Alexander A. Sherstov
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. STOC (2010)
Alexander A. Sherstov
Optimal bounds for sign-representing the intersection of two halfspaces by polynomials CoRR (2009)
Adam R. Klivans, Alexander A. Sherstov
Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. 75 (1) (2009)
Alexander A. Sherstov
from Depth-2 Majority Circuits. SIAM J. Comput. 38 (6) (2009)
Alexander A. Sherstov
The intersection of two halfspaces has high threshold degree. Electron. Colloquium Comput. Complex. 16 (2009)
Alexander A. Sherstov
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Comput. Complex. 18 (2) (2009)
Alexander A. Sherstov
On Quantum-Classical Equivalence for Composed Communication Problems CoRR (2009)
Alexander A. Sherstov
The Intersection of Two Halfspaces Has High Threshold Degree. FOCS (2009)
Alexander A. Sherstov
The intersection of two halfspaces has high threshold degree CoRR (2009)
Alexander A. Sherstov
The Pattern Matrix Method (Journal Version) CoRR (2009)
Alexander A. Sherstov
The Unbounded-Error Communication Complexity of Symmetric Functions. FOCS (2008)
Alexander A. Razborov, Alexander A. Sherstov
The Sign-Rank of AC^O. FOCS (2008)
Alexander A. Sherstov
Communication Complexity under Product and Nonproduct Distributions. Computational Complexity Conference (2008)
Alexander A. Sherstov
Halfspace Matrices. Comput. Complex. 17 (2) (2008)
Alexander A. Sherstov
Communication Lower Bounds Using Dual Polynomials. Electron. Colloquium Comput. Complex. 15 (057) (2008)
Alexander A. Sherstov
Communication Lower Bounds Using Dual Polynomials CoRR (2008)
Alexander A. Sherstov
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Computational Complexity Conference (2008)
Alexander A. Sherstov
Communication Lower Bounds Using Dual Polynomials. Bull. EATCS 95 (2008)
Alexander A. Sherstov
The pattern matrix method for lower bounds on quantum communication. STOC (2008)
Alexander A. Razborov, Alexander A. Sherstov
The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. 15 (016) (2008)
Alexander A. Sherstov
from depth-2 majority circuits. STOC (2007)
Alexander A. Sherstov
Unbounded-Error Communication Complexity of Symmetric Functions. Electron. Colloquium Comput. Complex. 14 (112) (2007)
Alexander A. Sherstov
Powering requires threshold depth 3. Inf. Process. Lett. 102 (2-3) (2007)
Alexander A. Sherstov
Communication Complexity under Product and Nonproduct Distributions. Electron. Colloquium Comput. Complex. 14 (072) (2007)
Alexander A. Sherstov
Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Electron. Colloquium Comput. Complex. 14 (116) (2007)
Alexander A. Sherstov
Halfspace Matrices. Computational Complexity Conference (2007)
Alexander A. Sherstov
The Pattern Matrix Method for Lower Bounds on Quantum Communication. Electron. Colloquium Comput. Complex. 14 (100) (2007)
Adam R. Klivans, Alexander A. Sherstov
A Lower Bound for Agnostically Learning Disjunctions. COLT (2007)
Adam R. Klivans, Alexander A. Sherstov
Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn. 69 (2-3) (2007)
Adam R. Klivans, Alexander A. Sherstov
Improved Lower Bounds for Learning Intersections of Halfspaces. COLT (2006)
Adam R. Klivans, Alexander A. Sherstov
Cryptographic Hardness Results for Learning Intersections of Halfspaces. Electron. Colloquium Comput. Complex. 13 (057) (2006)

Alexander A. Sherstov.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexander A. Sherstov