We consider a very wide class of models for sparse random Boolean 2CSPs; equivalently, degree-2 optimization problems over {problems over {±1}ⁿ. Specifically, we look at models ℳ 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 ℳ, we identify the "high probability value" s^*_ℳ of the natural SDP relaxation (equivalently, the quantum value). That is, for all > 0 we show that the SDP optimum of a random n-variable instance is (when normalized by n) in the range (s^*_ℳ - ∈, s^*_ℳ + ∈) with high probability.

32 pages

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

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by reports@cs.cmu.edu