Under construction, but perhaps the following blurb will suffice for now.

Much of my recent research is on lower bound problems. Roughly, it amounts to exploring the famous P vs NP problem in weaker models of computation. In particular, I work on various lower bound problems related to Geometric Proof Systems and inapproximability in Linear and Semidefinite optimization. Here is a link to a report. The paper gives an introduction and several pointers to recent literature in this area. My old webpage at UChicago.

Selected Research Papers

Complexity Theory and Lower Bounds

  • Approximation Resistance and Linear Programming Duality , joint with Subhash Khot and Madhur Tulsiani. An expository article, under preparation.
  • A Characterization of Strong Approximation Resistance, joint with Subhash Khot and Madhur Tulsiani, 2013.
  • The Complexity of Somewhat Approximation Resistant Predicates, joint with Subhash Khot and Madhur Tulsiani, 2012. See here (courtesy Simons Institute) for slides etc.
  • A Short Excursion into Semi-Algebraic Hierarchies, 2012. A survey of selected recent developments in the area.
  • LS+ Lower Bounds from Pairwise Independence, joint with Madhur Tulsiani, 2012.
  • Rank Bounds for a Hierarchy of Lov\'{a}sz and Schrijver, 2011.

  • Algorithms and Combinatorics

  • Total Acquisition in Graphs, joint with Tim LeSaulinier, Noah Prince, Paul Wenger, and Douglas West, 2011.
  • Testing Contractibility in Planar Rips Complexes, joint with Erin Chambers and Jeff Erickson, 2008.
  • Computing the Shortest Essential Cycle, joint with Jeff Erickson, 2007.

  • Errata for A Characterization of Approximation Resistance.

  • Note that the above is just an informal listing collected here for convenience. The dates refer to the time of a first preprint and not to any publication date. Here is a list of some recent research reports and another to some older publications.