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
∙
03/01/2023
Is Planted Coloring Easier than Planted Clique?
We study the computational complexity of two related problems: recoverin...
research
∙
07/30/2022
Polynomial-Time Power-Sum Decomposition of Polynomials
We give efficient algorithms for finding power-sum decomposition of an i...
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
∙
06/24/2021
Certifying solution geometry in random CSPs: counts, clusters and balance
An active topic in the study of random constraint satisfaction problems ...
research
∙
11/04/2019
