Computer Science 5th Year Masters Thesis Presentation

  • Remote Access - Zoom
  • Virtual Presentation - ET
  • Masters Student
  • Computer Science Department
  • Carnegie Mellon University
Master's Thesis Presentation

The SDP value of random 2CSPs

We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over { -1,+1}^n. Specifically, we look at models M which can be represented by matrix weighted polynomials over indeterminates taking the values of either matching matrices or permutation matrices. We interpret these polynomials also as models of graphs with matrix weighted edges. For each model M, we identify the “high probability value” s*_M  of the natural SDP relaxation (equivalently, the quantum value). That is, for all epsilon > 0, we show that the SDP optimum of a random n-variable instance is (when normalized by n) in the range (s*_M - epsilon, s*_M + epsilon) with high probability.

Zoom Particpation. See announcement.

Additional Information.

Thesis Committee:
Ryan O'Donnell (Advisor)
Pravesh Kothari

For More Information, Please Contact: