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.