Computer Science 5th Year Masters Thesis Presentation

Tuesday, August 6, 2019 - 11:00am

Location:

3001 Newell-Simon Hall

Speaker:

CORWIN DE BOOR, Masters Student /CORWIN%20DE%20BOOR

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:

Keywords:

Master's Thesis Presentation