7 papers
Rigorous Implications of the Low-Degree Heuristic
Jun-Ting Hsieh, Daniel M. Kane, Pravesh K. Kothari +3
Over the past decade, the low-degree heuristic has been used to estimate the algorithmic thresholds for a wide range of average-case planted vs null distinguishing problems. Such r…
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…
Sparsifying Sums of Positive Semidefinite Matrices
Arpon Basu, Pravesh K. Kothari, Yang P. Liu +1
In this paper, we revisit spectral sparsification for sums of arbitrary positive semidefinite (PSD) matrices. Concretely, for any collection of PSD matrices $\mathcal{A} = \{A_1, A…
The Quasi-Polynomial Low-Degree Conjecture is False
Rares-Darius Buhai, Jun-Ting Hsieh, Aayush Jain +1
There is a growing body of work on proving hardness results for average-case estimation problems by bounding the low-degree advantage (LDA) - a quantitative estimate of the closene…
Sum-Of-Squares To Approximate Knapsack
Pravesh K. Kothari, Sherry Sarkar
These notes give a self-contained exposition of Karlin, Mathieu and Nguyen's tight estimate of the integrality gap of the sum-of-squares semidefinite program for solving the knapsa…
Improved Lower Bounds for all Odd-Query Locally Decodable Codes
Arpon Basu, Jun-Ting Hsieh, Pravesh K. Kothari +1
We prove that for every odd , any -query binary, possibly non-linear locally decodable code (-LDC) must satisfy $k \leq \tilde{…