Alexander A. Sherstov

111 papers A* 24A 5Journal 79Unranked 3

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	The Approximate Degree of DNF and CNF Formulas. SIAM J. Comput. Alexander A. Sherstov
2024	A*	`conf`	The Communication Complexity of Approximating Matrix Rank. FOCS Alexander A. Sherstov, Andrey A. Storozhenko
2024	J	`jnl`	The Communication Complexity of Approximating Matrix Rank. CoRR Alexander A. Sherstov, Andrey A. Storozhenko
2024	J	`jnl`	The Communication Complexity of Approximating Matrix Rank. Electron. Colloquium Comput. Complex. Alexander A. Sherstov, Andrey A. Storozhenko
2023	J	`jnl`	An Optimal Separation of Randomized and Quantum Query Complexity. SIAM J. Comput. Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
2022	J	`jnl`	The Approximate Degree of DNF and CNF Formulas. CoRR Alexander A. Sherstov
2022	J	`jnl`	The Approximate Degree of DNF and CNF Formulas. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2022	A*	`conf`	The approximate degree of DNF and CNF formulas. STOC Alexander A. Sherstov
2021	A*	`conf`	An optimal separation of randomized and Quantum query complexity. STOC Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
2021	J	`jnl`	Quantum communication complexity of distribution testing. Quantum Inf. Comput. Aleksandrs Belovs, Arturo Castellanos, Francois Le Gall, Guillaume Malod, Alexander A. Sherstov
2021	J	`jnl`	The hardest halfspace. Comput. Complex. Alexander A. Sherstov
2020	J	`jnl`	Algorithmic Polynomials. SIAM J. Comput. Alexander A. Sherstov
2020	J	`jnl`	An Optimal Separation of Randomized and Quantum Query Complexity. CoRR Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
2020	J	`jnl`	An Optimal Separation of Randomized and Quantum Query Complexity. Electron. Colloquium Comput. Complex. Alexander A. Sherstov, Andrey A. Storozhenko, Pei Wu
2020	J	`jnl`	Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. ACM Trans. Comput. Theory Vladimir V. Podolskii, Alexander A. Sherstov
2020	J	`jnl`	Quantum Communication Complexity of Distribution Testing. CoRR Aleksandrs Belovs, Arturo Castellanos, François Le Gall, Guillaume Malod, Alexander A. Sherstov
2019	J	`jnl`	Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC$^0$. SIAM J. Comput. Alexander A. Sherstov, Pei Wu
2019	J	`jnl`	Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. CoRR Alexander A. Sherstov, Pei Wu
2019	J	`jnl`	Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. Alexander A. Sherstov, Pei Wu
2019	A*	`conf`	Near-optimal lower bounds on the threshold degree and sign-rank of AC STOC Alexander A. Sherstov, Pei Wu
2019	J	`jnl`	Optimal Interactive Coding for Insertions, Deletions, and Substitutions. IEEE Trans. Inf. Theory Alexander A. Sherstov, Pei Wu
2019	J	`jnl`	The Hardest Halfspace. CoRR Alexander A. Sherstov
2019	J	`jnl`	The hardest halfspace. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2019	J	`jnl`	Vanishing-Error Approximate Degree and QMA Complexity. CoRR Alexander A. Sherstov, Justin Thaler
2019	J	`jnl`	Vanishing-Error Approximate Degree and QMA Complexity. Electron. Colloquium Comput. Complex. Alexander A. Sherstov, Justin Thaler
2018	J	`jnl`	Algorithmic Polynomials. CoRR Alexander A. Sherstov
2018	A*	`conf`	Algorithmic polynomials. STOC Alexander A. Sherstov
2018	J	`jnl`	Algorithmic polynomials. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2018	J	`jnl`	Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. SIAM J. Comput. Alexander A. Sherstov
2018	J	`jnl`	Compressing Interactive Communication Under Product Distributions. SIAM J. Comput. Alexander A. Sherstov
2018	J	`jnl`	On Multiparty Communication with Large versus Unbounded Error. Theory Comput. Alexander A. Sherstov
2018	J	`jnl`	The Power of Asymmetry in Constant-Depth Circuits. SIAM J. Comput. Alexander A. Sherstov
2017	J	`jnl`	Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. CoRR Vladimir V. Podolskii, Alexander A. Sherstov
2017	J	`jnl`	Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. Electron. Colloquium Comput. Complex. Vladimir V. Podolskii, Alexander A. Sherstov
2017	A*	`conf`	Optimal Interactive Coding for Insertions, Deletions, and Substitutions. FOCS Alexander A. Sherstov, Pei Wu
2017	J	`jnl`	Optimal Interactive Coding for Insertions, Deletions, and Substitutions. Electron. Colloquium Comput. Complex. Alexander A. Sherstov, Pei Wu
2016	A*	`conf`	Bounded-Communication Leakage Resilience via Parity-Resilient Circuits. FOCS Vipul Goyal, Yuval Ishai, Hemanta K. Maji, Amit Sahai, Alexander A. Sherstov
2016	A*	`conf`	Compressing Interactive Communication under Product Distributions. FOCS Alexander A. Sherstov
2016	J	`jnl`	Compressing interactive communication under product distributions. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2016	J	`jnl`	On multiparty communication with large versus unbounded error. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2016	J	`jnl`	The Multiparty Communication Complexity of Set Disjointness. SIAM J. Comput. Alexander A. Sherstov
2015	A*	`conf`	The Power of Asymmetry in Constant-Depth Circuits. FOCS Alexander A. Sherstov
2015	J	`jnl`	The Power of Asymmetry in Constant-Depth Circuits. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2014	J	`jnl`	Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2014	A*	`conf`	Breaking the minsky-papert barrier for constant-depth circuits. STOC Alexander A. Sherstov
2014	—	`conf`	Communication Complexity Theory: Thirty-Five Years of Set Disjointness. MFCS (1) Alexander A. Sherstov
2014	J	`jnl`	Communication Lower Bounds Using Directional Derivatives. J. ACM Alexander A. Sherstov
2013	J	`jnl`	Approximating the AND-OR Tree. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2013	J	`jnl`	Approximating the AND-OR Tree. Theory Comput. Alexander A. Sherstov
2013	J	`jnl`	Communication Lower Bounds Using Directional Derivatives. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2013	A*	`conf`	Communication lower bounds using directional derivatives. STOC Alexander A. Sherstov
2013	J	`jnl`	Making Polynomials Robust to Noise. Theory Comput. Alexander A. Sherstov
2013	J	`jnl`	Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Comb. Alexander A. Sherstov
2013	J	`jnl`	The Intersection of Two Halfspaces Has High Threshold Degree. SIAM J. Comput. Alexander A. Sherstov
2012	J	`jnl`	Making Polynomials Robust to Noise. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2012	A*	`conf`	Making polynomials robust to noise. STOC Alexander A. Sherstov
2012	J	`jnl`	Strong Direct Product Theorems for Quantum Communication and Query Complexity. SIAM J. Comput. Alexander A. Sherstov
2012	J	`jnl`	The Communication Complexity of Gap Hamming Distance. Theory Comput. Alexander A. Sherstov
2012	A*	`conf`	The multiparty communication complexity of set disjointness. STOC Alexander A. Sherstov
2011	J	`jnl`	Strong Direct Product Theorems for Quantum Communication and Query Complexity. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2011	A*	`conf`	Strong direct product theorems for quantum communication and query complexity. STOC Alexander A. Sherstov
2011	J	`jnl`	The Communication Complexity of Gap Hamming Distance. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2011	J	`jnl`	The Multiparty Communication Complexity of Set Disjointness. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2011	J	`jnl`	The Pattern Matrix Method. SIAM J. Comput. Alexander A. Sherstov
2011	J	`jnl`	The unbounded-error communication complexity of symmetric functions. Comb. Alexander A. Sherstov
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity CoRR Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity. Electron. Colloquium Comput. Complex. Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	A Separation of NP and coNP in Multiparty Communication Complexity. Theory Comput. Dmitry Gavinsky, Alexander A. Sherstov
2010	J	`jnl`	Communication Complexity Under Product and Nonproduct Distributions. Comput. Complex. Alexander A. Sherstov
2010	J	`jnl`	Lower Bounds for Agnostic Learning via Approximate Rank. Comput. Complex. Adam R. Klivans, Alexander A. Sherstov
2010	J	`jnl`	On quantum-classical equivalence for composed communication problems. Quantum Inf. Comput. Alexander A. Sherstov
2010	A*	`conf`	Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. STOC Alexander A. Sherstov
2010	J	`jnl`	Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2010	J	`jnl`	Strong direct product theorems for quantum communication and query complexity CoRR Alexander A. Sherstov
2010	J	`jnl`	The Sign-Rank of AC SIAM J. Comput. Alexander A. Razborov, Alexander A. Sherstov
2009	J	`jnl`	Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Comput. Complex. Alexander A. Sherstov
2009	J	`jnl`	Cryptographic hardness for learning intersections of halfspaces. J. Comput. Syst. Sci. Adam R. Klivans, Alexander A. Sherstov
2009	J	`jnl`	On Quantum-Classical Equivalence for Composed Communication Problems CoRR Alexander A. Sherstov
2009	J	`jnl`	Optimal bounds for sign-representing the intersection of two halfspaces by polynomials CoRR Alexander A. Sherstov
2009	J	`jnl`	SeparatingAC SIAM J. Comput. Alexander A. Sherstov
2009	A*	`conf`	The Intersection of Two Halfspaces Has High Threshold Degree. FOCS Alexander A. Sherstov
2009	J	`jnl`	The Pattern Matrix Method (Journal Version) CoRR Alexander A. Sherstov
2009	J	`jnl`	The intersection of two halfspaces has high threshold degree CoRR Alexander A. Sherstov
2009	J	`jnl`	The intersection of two halfspaces has high threshold degree. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2008	A	`conf`	Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. CCC Alexander A. Sherstov
2008	A	`conf`	Communication Complexity under Product and Nonproduct Distributions. CCC Alexander A. Sherstov
2008	J	`jnl`	Communication Lower Bounds Using Dual Polynomials CoRR Alexander A. Sherstov
2008	J	`jnl`	Communication Lower Bounds Using Dual Polynomials. Bull. EATCS Alexander A. Sherstov
2008	J	`jnl`	Communication Lower Bounds Using Dual Polynomials. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2008	J	`jnl`	Halfspace Matrices. Comput. Complex. Alexander A. Sherstov
2008	J	`jnl`	The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. Alexander A. Razborov, Alexander A. Sherstov
2008	A*	`conf`	The Sign-Rank of AC^O. FOCS Alexander A. Razborov, Alexander A. Sherstov
2008	A*	`conf`	The Unbounded-Error Communication Complexity of Symmetric Functions. FOCS Alexander A. Sherstov
2008	A*	`conf`	The pattern matrix method for lower bounds on quantum communication. STOC Alexander A. Sherstov
2007	A*	`conf`	A Lower Bound for Agnostically Learning Disjunctions. COLT Adam R. Klivans, Alexander A. Sherstov
2007	J	`jnl`	Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2007	J	`jnl`	Communication Complexity under Product and Nonproduct Distributions. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2007	A	`conf`	Halfspace Matrices. CCC Alexander A. Sherstov
2007	J	`jnl`	Powering requires threshold depth 3. Inf. Process. Lett. Alexander A. Sherstov
2007	A*	`conf`	Separating AC STOC Alexander A. Sherstov
2007	J	`jnl`	The Pattern Matrix Method for Lower Bounds on Quantum Communication. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2007	J	`jnl`	Unbounded-Error Communication Complexity of Symmetric Functions. Electron. Colloquium Comput. Complex. Alexander A. Sherstov
2007	J	`jnl`	Unconditional lower bounds for learning intersections of halfspaces. Mach. Learn. Adam R. Klivans, Alexander A. Sherstov
2006	J	`jnl`	Cryptographic Hardness Results for Learning Intersections of Halfspaces. Electron. Colloquium Comput. Complex. Adam R. Klivans, Alexander A. Sherstov
2006	A*	`conf`	Cryptographic Hardness for Learning Intersections of Halfspaces. FOCS Adam R. Klivans, Alexander A. Sherstov
2006	A*	`conf`	Improved Lower Bounds for Learning Intersections of Halfspaces. COLT Adam R. Klivans, Alexander A. Sherstov
2005	—	`conf`	Function Approximation via Tile Coding: Automating Parameter Choice. SARA Alexander A. Sherstov, Peter Stone
2005	A*	`conf`	Improving Action Selection in MDP's via Knowledge Transfer. AAAI Alexander A. Sherstov, Peter Stone
2004	—	`conf`	Three Automated Stock-Trading Agents: A Comparative Study. AMEC Alexander A. Sherstov, Peter Stone
2003	A	`conf`	Distributed visualization of graph algorithms. SIGCSE Alexander A. Sherstov
2002	A	`conf`	Using Java to design and test hardware circuits over a classroom network. SIGCSE Michael J. Jipping, Steve Marlowe, Alexander A. Sherstov