Computer Science 5th Year Masters Thesis Presentation

Tuesday, August 6, 2019 - 11:00am


3001 Newell-Simon Hall



In Search of Degree-4 Sum-of-Squares Lower Bounds for MaxCut

The behavior of MaxCut on large, regular, random undirected graphs is well understood up to third-order terms. Even so, we do not yet know of efficient algorithms for finding the MaxCut. The sum-ofsquares (SOS) algorithm family, containing our best-known approximation algorithms, does not well approximate the MaxCut on these random graphs for degree-2. As SOS gets more powerful with increasing degree, does this result hold up for degree-4 as well? In this work, we develop a technique for extending degree-2 pseudoexpectations, objects showing inapproximability, to degree-4 pseudoexpectations. We identify configuration-symmetry as a key property of these pseudo-expectations, and bound the effects of glitches that prevent natural extension. By analyzing the glitches more carefully, one may be able to obtain degree-4 SOS lower-bounds.

Thesis Committee:
Ryan O'Donnell
Venkatesan Guruswami

For More Information, Contact:


Master's Thesis Presentation