Alexander Sherstov

Associate Professor
Computer Science Department
UCLA

 

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. My research is supported by an NSF CAREER award and a Sloan Research Fellowship.

 

  Curriculum Vitae

  Research Statement

 

PH.D. THESIS

Lower bounds in communication complexity and learning theory via analytic methods
University of Texas at Austin, 2009
Download

 

PUBLICATIONS

Algorithmic polynomials
A. A. Sherstov
Forthcoming, November 2017

Optimal interactive coding for insertions, deletions, and substitutions
A. A. Sherstov, P. Wu
FOCS 2017
Download

On multiparty communication with large versus unbounded error
A. A. Sherstov
Theory of Computing, 2017. To appear.
Download

Compressing interactive communication under product distributions
A. A. Sherstov
FOCS 2016
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
Invited to appear in a special issue of SIAM Journal on Computing for FOCS 2015
Download

Breaking the Minsky-Papert barrier for constant-depth circuits
A. A. Sherstov
STOC 2014
To appear in SIAM Journal on Computing. (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