Research

My research is in theoretical computer science. My research interests include complexity theory (in particular, communication complexity, circuit complexity, and analytic measures of complexity), computational learning theory, and quantum computing.

Lower bounds in communication complexity and learning theory via analytic methods Ph.D. Thesis University of Texas at Austin, August 2009

PUBLICATIONS

• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials.
  A. A. Sherstov
  Manuscript on arXiv, October 2009.
    Download
  
  
• The intersection of two halfspaces has high threshold degree.
  A. A. Sherstov
  FOCS 2009
  BEST STUDENT PAPER AWARD
    Download
  
  
• On quantum-classical equivalence for composed communication problems.
  A. A. Sherstov
  Manuscript at quant-ph/0906.1399, June 2009.
    Download
  
  
• The sign-rank of AC⁰.
  A. A. Razborov, A. A. Sherstov
  FOCS 2008
  To appear in SIAM Journal on Computing, 2010.
    Download
  
  
• The unbounded-error communication complexity of symmetric functions.
  A. A. Sherstov
  FOCS 2008
  Journal version: accepted to Combinatorica.
    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
  To appear in SIAM Journal on Computing (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
  Journal version: 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
  Journal version: Computational Complexity, 2009. To appear.
    Download
  
  
• Halfspace matrices.
  A. A. Sherstov
  CCC 2007
  BEST STUDENT PAPER AWARD
  Journal version: Computational Complexity, 17(2):149-178, 2008.
     (Special issue for CCC 2007.)
    Download
  
  
• Separating AC⁰ from depth-2 majority circuits.
  A. A. Sherstov
  STOC 2007
  Journal version: 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
    Download
  
  
• Cryptographic hardness for learning intersections of halfspaces.
  A. R. Klivans, A. A. Sherstov
  FOCS 2006
  Journal version: J. Computer and System Sciences, 75(1):2-12, 2009.
     (Invited paper, special issue on learning theory.)
    Download
  
  
• Unconditional lower bounds for learning intersections of halfspaces.
  A. R. Klivans, A. A. Sherstov
  COLT 2006
  BEST STUDENT PAPER AWARD
  Journal version: Machine Learning, 69(2-3):97-114, 2007.
     (Special issue on COLT 2007.)
    Download
  
  
• Powering requires threshold depth 3.
  A. A. Sherstov
  Journal version: Information Processing Letters, 102(2-3):104-107, 2007.
    Download
  
  

At the beginning of my Ph.D. program (2003-2004), I also did research in artificial intelligence. My projects focused on knowledge transfer, reinforcement learning, and electronic commerce. As part of my work, I co-organized the ICML 2004 Physiological Data Modeling workshop and contest.

PUBLICATIONS IN ARTIFICIAL INTELLIGENCE (2003-2004)

• 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