21 citations · 61 across the 21 of their papers we have counts for
Showing 2021Show all
3 papers · 1 filter
cs.CC2021
Sum-of-Squares Lower Bounds for Sparse Independent Set
Chris Jones, Aaron Potechin, Goutham Rajendran +2
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerful algorithmic paradigm which captures state-of-the-art algorithmic guarantees for a wide array of problems.…
cs.CC2021
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
Adam Kurpisz, Aaron Potechin, Elias Samuel Wirth
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean hypercube for Symmetric Quadratic Functions (SQFs) in variables with roots placed in points and $…
math.CO2021
Almost-Orthogonal Bases for Inner Product Polynomials
Chris Jones, Aaron Potechin
In this paper, we consider low-degree polynomials of inner products between a collection of random vectors. We give an almost orthogonal basis for this vector space of polynomials…