English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The degree-$4$ Sum-of-Squares (SoS) SDP relaxation is a powerful algorithmthat captures the best known polynomial time algorithms for a broad range ofproblems including MaxCut, Sparsest Cut, all MaxCSPs and tensor PCA. Despitebeing an explicit algorithm with relatively low computational complexity, thelimits of degree-$4$ SoS SDP are not well understood. For example, existingintegrality gaps do not rule out a $(2-\varepsilon)$-algorithm for Vertex Coveror a $(0.878+\varepsilon)$-algorithm for MaxCut via degree-$4$ SoS SDPs, eachof which would refute the notorious Unique Games Conjecture.  We exhibit an explicit mapping from solutions for degree-$2$ Sum-of-SquaresSDP (Goemans-Williamson SDP) to solutions for the degree-$4$ Sum-of-Squares SDPrelaxation on boolean variables. By virtue of this mapping, one can lift lowerbounds for degree-$2$ SoS SDP relaxation to corresponding lower bounds fordegree-$4$ SoS SDPs. We use this approach to obtain degree-$4$ SoS SDP lowerbounds for MaxCut on random $d$-regular graphs, Sherington-Kirkpatrick modelfrom statistical physics and PSD Grothendieck problem.  Our constructions use the idea of pseudocalibration towards candidate SDPvectors, while it was previously only used to produce the candidate matrixwhich one would show is PSD using much technical work. In addition, we developa different technique to bound the spectral norms of _graphical matrices_ thatarise in the context of SoS SDPs. The technique is much simpler and yieldsbetter bounds in many cases than the _trace method_ -- which was the soletechnique for this purpose.

Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$