research
∙
07/12/2023
Ellipsoid Fitting Up to a Constant
In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following el...
share
research
∙
03/30/2023
Sum-of-Squares Lower Bounds for Densest k-Subgraph
Given a graph and an integer k, Densest k-Subgraph is the algorithmic ta...
research
∙
12/21/2022
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Assuming the Unique Games Conjecture (UGC), the best approximation ratio...
research
∙
05/07/2022
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle
In this paper, we investigate the total coefficient size of Nullstellens...
research
∙
11/17/2021
Sum-of-Squares Lower Bounds for Sparse Independent Set
The Sum-of-Squares (SoS) hierarchy of semidefinite programs is a powerfu...
research
∙
07/08/2021
SoS certification for symmetric quadratic functions and its connection to constrained Boolean hypercube optimization
We study the rank of the Sum of Squares (SoS) hierarchy over the Boolean...
research
∙
07/01/2021
Almost-Orthogonal Bases for Inner Product Polynomials
In this paper, we consider low-degree polynomials of inner products betw...
research
∙
11/18/2020
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
In this paper we show that simple semidefinite programs inspired by degr...
research
∙
11/09/2020
Machinery for Proving Sum-of-Squares Lower Bounds on Certification Problems
In this paper, we construct general machinery for proving Sum-of-Squares...
research
∙
09/22/2020
On the Mysteries of MAX NAE-SAT
MAX NAE-SAT is a natural optimization problem, closely related to its be...
research
∙
09/03/2020
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-a...
research
∙
06/25/2020
The Spectrum of the Singular Values of Z-Shaped Graph Matrices
Graph matrices are a type of matrix which appears when analyzing the sum...
research
∙
07/09/2019
On the Approximability of Presidential Type Predicates
Given a predicate P: {-1, 1}^k →{-1, 1}, let CSP(P) be the set of constr...
research
∙
12/04/2018
Sum of squares bounds for the total ordering principle
In this paper, we analyze the sum of squares hierarchy (SOS) on the tota...
research
∙
07/12/2018
On the Approximation Resistance of Balanced Linear Threshold Functions
In this paper, we show that there exists a balanced linear threshold fun...
research
∙
02/13/2018
Lengths of Words Accepted by Nondeterministic Finite Automata
We consider two natural problems about nondeterministic finite automata....
research
∙
11/30/2017
Sum of squares lower bounds from symmetry and a good story
In this paper, we develop machinery for proving sum of squares lower bou...
research
∙
10/13/2017
The power of sum-of-squares for detecting hidden structures
We study planted problems---finding hidden structures in random noisy in...
research
∙
09/10/2017
A Note on Property Testing Sum of Squares and Multivariate Polynomial Interpolation
In this paper, we investigate property testing whether or not a degree d...
research
∙
02/21/2017