Monday, May 10, 2021 - 1:00pm

Location:

Speaker:

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, Contact:

Keywords: