Sum of squares lower bounds from symmetry and a good story

DOI10.4230/LIPICS.ITCS.2019.61MaRDI QIDQ5090440FDOQ5090440

Authors: Aaron Potechin 

Publication date: 18 July 2022

Full work available at URL: https://arxiv.org/abs/1711.11469

Recommendations

• Item:QQ2191774
• Item:QQ2191774
• On the sum-of-squares degree of symmetric quadratic functions
• SOS lower bounds with hard constraints: think global, act local
• Sum of squares lower bounds for refuting any CSP

zbMATH Keywords

graph theorylower boundsproof complexitysum of squares hierarchy

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Global optimization with polynomials and the problem of moments
• Flag algebras
• Symmetry groups, semidefinite programs, and sums of squares
• Expander flows, geometric embeddings and graph partitioning
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On Sets of Acquaintances and Strangers at any Party
• Sum of squares lower bounds from pairwise independence (extended abstract)
• Sums of squares on the hypercube
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• Title not available (Why is that?)
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Subexponential algorithms for unique games and related problems
• Rounding sum-of-squares relaxations
• CSP gaps and reductions in the lasserre hierarchy
• Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
• Complexity of Positivstellensatz proofs for the knapsack
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Symmetric sums of squares over \(k\)-subset hypercubes
• Sum of squares lower bounds for refuting any CSP
• Sum-of-squares Lower Bounds for Planted Clique
• On the sum-of-squares degree of symmetric quadratic functions
• Dictionary learning and tensor decomposition via the sum-of-squares method
• Decomposing overcomplete 3rd order tensors using sum-of-squares algorithms
• Quantum entanglement, sum of squares, and the log rank conjecture
• On the integrality gap of degree-4 sum of squares for planted clique

Cited In (5)

• Perfect matching in random graphs is as hard as Tseitin
• Sum of squares bounds for the ordering principle
• Tropicalization of graph profiles
• Sum-of-squares bounds via Boolean function analysis
• The Spectrum of the Grigoriev–Laurent Pseudomoments

This page was built for publication: Sum of squares lower bounds from symmetry and a good story

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090440)