5 citations · 6 across the 8 of their papers we have counts for
10 papers
Certifiable Near-Optimality: A Simple Framework for Unifying Search and Refutation for (Semi)random CSPs
Prashanti Anderson, Peter Manohar, Jeff Xu
A classical problem in average-case complexity is the study of random constraint satisfaction problems (CSPs). Random CSPs are traditionally studied in two different settings: refu…
Sharp Phase Transition for Ellipsoid Fitting
Sofia de la Cerda, Aaron Potechin, Madhur Tulsiani +1
We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for independent Gaussian points in dimensi…
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Pravesh K. Kothari, Jeff Xu
In this work, we revisit algorithms for Tensor PCA: given an order- tensor of the form where is a random symmetric Gaussian tensor with unit var…
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
We prove that for every , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…
Ellipsoid Fitting Up to a Constant
Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin +1
In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest such that there is an ellipsoid in th…
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein +1
We study the computational complexity of two related problems: recovering a planted -coloring in , and finding efficiently verifiable witnesses of non--colorability…
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari +1
We give efficient algorithms for finding power-sum decomposition of an input polynomial with component s. The case of linear s is equivale…
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.…
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the de…
Lifting Sum-of-Squares Lower Bounds: Degree- to Degree-
Sidhanth Mohanty, Prasad Raghavendra, Jeff Xu
The degree- Sum-of-Squares (SoS) SDP relaxation is a powerful algorithm that captures the best known polynomial time algorithms for a broad range of problems including MaxCut, S…