Monday, May 10, 2021 - 1:00pm
Location:
Virtual Presentation - ET Remote Access - ZoomSpeaker:
AMULYA MUSIPATLA, Masters Student https://www.linkedin.com/in/amusipatlaThe 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.
Thesis Committee:
Ryan O'Donnell (Advisor)
Pravesh Kothari