My research is in theoretical computer science. My interests include complexity theory (in particular, communication complexity and circuit complexity), computational learning theory, and quantum computing.
Research funding: NSF CCF-2220232 (current); NSF grant CCF-1814947; NSF CAREER award CCF-1149018 (2012-2018); Sloan Research Fellowship (2014-2018).
Ph.D. students: Alan Joel (Ph.D. in progress), Andrey Storozhenko (Ph.D. in progress), Pei Wu (Ph.D. 2021, now a postdoctoral fellow at the Institute for Advanced Study).
PH.D. THESIS
Lower bounds in communication complexity and learning theory via analytic methods
University of Texas at Austin, 2009
Download
PUBLICATIONS
The communication complexity of approximating matrix rank
A. A. Sherstov, A. A. Storozhenko
FOCS 2024
Download
The approximate degree of DNF and CNF formulas
A. A. Sherstov
STOC 2022
Download
An optimal separation of randomized and quantum query complexity
A. A. Sherstov, A. A. Storozhenko, and P. Wu
STOC 2021
QIP 2021 contributed talk
SIAM Journal on Computing, 52(2):525–567, 2023.
Download
Quantum communication complexity of distribution testing
A. Belovs, A. Castellanos, F. Le Gall, G. Malod, A. A. Sherstov
Quantum Information and Computation,
21(15-16):1261–1273, 2021.
Download
The hardest halfspace
A. A. Sherstov
Computational Complexity, 30(11):1–85, 2021.
Download
Vanishing-error approximate degree and QMA complexity
A. A. Sherstov, J. Thaler
To appear in Chicago Journal of Theoretical Computer Science, 2022.
Download
Near-optimal lower bounds on the threshold degree and sign-rank of AC0
A. A. Sherstov, P. Wu
STOC 2019
SIAM Journal on Computing, 52(2):STOC19-1-STOC19-86, 2021.
(Special issue for STOC 2019)
Download
Algorithmic polynomials
A. A. Sherstov
STOC 2018
SIAM Journal on Computing, 49(6):1173–1231, 2020.
Download
Inner product and set disjointness: Beyond logarithmically many parties
V. V. Podolskii, A. A. Sherstov
ACM Transactions on Computation Theory, 12(4): 26:1–26:28, 2020.
Download
Optimal interactive coding for insertions, deletions, and substitutions
A. A. Sherstov, P. Wu
FOCS 2017
IEEE Transactions on Information Theory, 65(10):5971–6000, 2019.
Download
On multiparty communication with large versus unbounded error
A. A. Sherstov
Theory of Computing, 14(22):1–17, 2018.
Download
Compressing interactive communication under product distributions
A. A. Sherstov
FOCS 2016
SIAM Journal on Computing, 47(2):367–419, 2018.
Download
Bounded-communication leakage resilience via parity-resilient circuits
V. Goyal, Y. Ishai, H. K. Maji, A. Sahai, A. A. Sherstov
FOCS 2016
Download
The power of asymmetry in constant-depth circuits
A. A. Sherstov
FOCS 2015
SIAM Journal on Computing, 47(6):2362–2434, 2018. (Special issue for FOCS 2015)
Download
Breaking the Minsky-Papert barrier for constant-depth circuits
A. A. Sherstov
STOC 2014
SIAM Journal on Computing, 47(5):1809-1857, 2018. (Special issue for STOC 2014)
Download
Communication complexity theory: Thirty-five years of set disjointness
A. A. Sherstov
MFCS 2014, invited paper
Download
Approximating the AND-OR tree
A. A. Sherstov
Theory of Computing, 9(20):653–663, 2013
Download
Communication lower bounds using directional derivatives
A. A. Sherstov
STOC 2013
Journal of the ACM, 61(6):1–71, 2014
Invited to appear in SIAM Journal on Computing (declined in favor of J. ACM)
Download
Making polynomials robust to noise
A. A. Sherstov
STOC 2012
Theory of Computing, 9(18):593–615, 2013. (Special issue on Boolean function analysis)
Download
The multiparty communication complexity of set disjointness
A. A. Sherstov
STOC 2012
SIAM Journal on Computing, 45(4):1450–1489, 2016.
(Special issue for STOC 2012)
Download
The communication complexity of gap Hamming distance
A. A. Sherstov
Theory of Computing, 8(8):197–208, 2012
Download
Strong direct product theorems for quantum communication and query
complexity
A. A. Sherstov
STOC 2011
SIAM Journal on Computing, 41(5):1122–1165, 2012
Download
A separation of NP and coNP in multiparty communication complexity
D. Gavinsky, A. A. Sherstov
Theory of Computing, 6(1):227–245, 2010
Download
Optimal bounds for sign-representing the intersection of two halfspaces
by polynomials
A. A. Sherstov
STOC 2010
Combinatorica, 33(1):73–96, 2013
Download
The intersection of two halfspaces has high threshold degree
A. A. Sherstov
FOCS 2009
BEST STUDENT PAPER AWARD
SIAM Journal on Computing, 42(6):2329–2374, 2013.
(Special issue for FOCS 2009)
Download
On quantum-classical equivalence for composed communication problems
A. A. Sherstov
Quantum Information & Computation, 10(5–6):435–455, 2010
Download
The sign-rank of AC0
A. A. Razborov, A. A. Sherstov
FOCS 2008
SIAM Journal on Computing, 39(5):1833–1855, 2010
Download
The unbounded-error communication complexity of symmetric functions
A. A. Sherstov
FOCS 2008
Combinatorica, 31(5):583–614, 2011
Download
Communication lower bounds using dual polynomials
A. A. Sherstov
Bulletin of the EATCS, 95:59–93, 2008
INVITED SURVEY ARTICLE
Download
The pattern matrix method
A. A. Sherstov
STOC 2008
SIAM Journal on Computing, 40(6):1969–2000, 2011. (Special issue for STOC 2008)
Original title: "The pattern matrix method for lower bounds on quantum
communication"
Download
Approximate inclusion-exclusion for arbitrary symmetric functions
A. A. Sherstov
CCC 2008
BEST STUDENT PAPER AWARD
Computational Complexity, 18(2):219–247, 2009. (Special issue for CCC 2008)
Download
Communication complexity under product and nonproduct distributions
A. A. Sherstov
CCC 2008
Computational Complexity, 19(1):135–150, 2010
Download
Halfspace matrices
A. A. Sherstov
CCC 2007
BEST STUDENT PAPER AWARD
Computational Complexity, 17(2):149–178, 2008.
(Special issue for CCC 2007)
Download
Separating AC0 from depth-2 majority circuits
A. A. Sherstov
STOC 2007
SIAM Journal on Computing, 38(6):2113–2129, 2009
Download
A lower bound for agnostically learning disjunctions
A. R. Klivans, A. A. Sherstov
COLT 2007
Computational Complexity, 19(4):581–604, 2010
Download
Cryptographic hardness for learning intersections of halfspaces
A. R. Klivans, A. A. Sherstov
FOCS 2006
J. Computer and System Sciences, 75(1):2–12, 2009.
(Special issue on learning)
Download
Unconditional lower bounds for learning intersections of halfspaces
A. R. Klivans, A. A. Sherstov
COLT 2006
BEST STUDENT PAPER AWARD
Machine Learning, 69(2–3):97–114, 2007.
(Special issue for COLT 2006)
Download
Powering requires threshold depth 3
A. A. Sherstov
Information Processing Letters, 102(2–3):104–107, 2007
Download
ARTIFICIAL INTELLIGENCE (2003–04)
Improving action selection in MDP's via knowledge transfer.
A. A. Sherstov, P. Stone
20th National Conference on Artificial Intelligence
(AAAI), 2005.
Download
Function approximation via tile coding: Automating parameter choice
A. A. Sherstov, P. Stone
6th Symposium on Abstraction, Reformulation, and Approximation
(SARA), 2005.
Download
Three automated stock-trading agents: A comparative study
A. A. Sherstov, P. Stone
6th AAMAS Workshop on Agent Mediated Electronic Commerce (AMEC),
2004.
Download