Home Research Teaching Contact
Research on the Sum of Squares Hierarchy (SoS) and Graph Matrices


Overview:
The sum of squares hierarchy (SoS) is a model of computation which has the following nice properties:
  1. SoS is broadly applicable.
  2. SoS is surprisingly powerful.
  3. In some sense, SoS is simple as all it uses are polynomial equalities and the fact that squares are non-negative over the real numbers.
For more information about SoS, see the following links:
  1. My course on SoS.
  2. Boaz Barak and David Steurer's survey on SoS.
  3. Tselil Schramm's course on SoS.
  4. Thomas Rothvoss's survey on the Lasserre hierarchy (which is another name for SoS).
  5. Boaz Barak, Pravesh Kothari, and David Steurer's course on SoS.
  6. Massimo Lauria's course on SoS.
  7. Toniann Pitassi's course on proof complexity, mathematical programming, and algorithms (which is largely about SoS).
Graph matrices are a type of matrix which arises naturally when studying SoS and other methods which use higher moments on average case problems. Currently, except for rough norm bounds, not much is known about graph matrices.

Papers: