Prasad Raghavendra

Pravesh Kothari, Anand Louis, Rameesh Paul et al.

We study the problem of efficiently certifying upper bounds on independence number of $\ell$-uniform hypergraphs in semirandom models. This is a notoriously hard problem, with efficient algorithms failing to approximate the independence number within an $n^{1-ε}$ factor in worst-case. A folklore reduction to graph case yields a weak $O(\sqrt{n/p})$ bound, and spectral certificates[GKM22] achieve $O(\sqrt{n}.polylog(n)/p^{2/\ell})$. In this work, we prove sharper bounds that eliminate logarithmic factors in $n$ and nearly attain the optimal threshold of $O(\sqrt{n}/p^{1/\ell})$. We also show matching low-degree polynomial lower bounds. Our certificates are designed using the proofs-to-algorithms paradigm via degree-$2\ell$ Sum-of-Squares(SoS) relaxation. The technically challenging case is odd-arity hypergraphs, where we employ a tensor-based analysis reducing the problem to bounding operator norm of random chaos matrices. Previous bounds[AMP21,RT23] have a logarithmic dependence, which we remove using recent matrix concentration inequalities[BBvH23,BLNvH25]; we believe this maybe useful in other hypergraph problems. Since we deploy our certificates in SoS framework, the bounds continue to hold for monotone adversaries. Additionally, we construct a 'quiet' planted distribution supported on independent sets of size $k=o(\sqrt{n}/p^{1/\ell})$ that is low-degree indistinguishable from random hypergraphs. Prior to this work, the problem of constructing a quiet planted distribution in sparse regimes was open even for graphs[JPR+22,Pot22]. This is in contrast to recovering a planted independent set, where the threshold is $k \gtrsim \sqrt{n}/p^{1/2(\ell-1)}$ (matching lower bounds in a concurrent work[FS26]). As application, our certificates combine with an SoS relaxation of an r-coloring system to recover a planted r-colorable subhypergraph under strong adversaries of [LPR25].

Parikshit Gopalan, Princewill Okoroafor, Prasad Raghavendra et al.

Consider the supervised learning setting where the goal is to learn to predict labels $\mathbf y$ given points $\mathbf x$ from a distribution. An \textit{omnipredictor} for a class $\mathcal L$ of loss functions and a class $\mathcal C$ of hypotheses is a predictor whose predictions incur less expected loss than the best hypothesis in $\mathcal C$ for every loss in $\mathcal L$. Since the work of [GKR+21] that introduced the notion, there has been a large body of work in the setting of binary labels where $\mathbf y \in \{0, 1\}$, but much less is known about the regression setting where $\mathbf y \in [0,1]$ can be continuous. Our main conceptual contribution is the notion of \textit{sufficient statistics} for loss minimization over a family of loss functions: these are a set of statistics about a distribution such that knowing them allows one to take actions that minimize the expected loss for any loss in the family. The notion of sufficient statistics relates directly to the approximate rank of the family of loss functions. Our key technical contribution is a bound of $O(1/\varepsilon^{2/3})$ on the $ε$-approximate rank of convex, Lipschitz functions on the interval $[0,1]$, which we show is tight up to a factor of $\mathrm{polylog} (1/ε)$. This yields improved runtimes for learning omnipredictors for the class of all convex, Lipschitz loss functions under weak learnability assumptions about the class $\mathcal C$. We also give efficient omnipredictors when the loss families have low-degree polynomial approximations, or arise from generalized linear models (GLMs). This translation from sufficient statistics to faster omnipredictors is made possible by lifting the technique of loss outcome indistinguishability introduced by [GKH+23] for Boolean labels to the regression setting.

Prasad Raghavendra, Tselil Schramm, David Steurer

Estimation is the computational task of recovering a hidden parameter $x$ associated with a distribution $D_x$, given a measurement $y$ sampled from the distribution. High dimensional estimation problems arise naturally in statistics, machine learning, and complexity theory. Many high dimensional estimation problems can be formulated as systems of polynomial equations and inequalities, and thus give rise to natural probability distributions over polynomial systems. Sum-of-squares proofs provide a powerful framework to reason about polynomial systems, and further there exist efficient algorithms to search for low-degree sum-of-squares proofs. Understanding and characterizing the power of sum-of-squares proofs for estimation problems has been a subject of intense study in recent years. On one hand, there is a growing body of work utilizing sum-of-squares proofs for recovering solutions to polynomial systems when the system is feasible. On the other hand, a general technique referred to as pseudocalibration has been developed towards showing lower bounds on the degree of sum-of-squares proofs. Finally, the existence of sum-of-squares refutations of a polynomial system has been shown to be intimately connected to the existence of spectral algorithms. In this article we survey these developments.

Moritz Hardt, Raghu Meka, Prasad Raghavendra et al.

Matrix Completion is the problem of recovering an unknown real-valued low-rank matrix from a subsample of its entries. Important recent results show that the problem can be solved efficiently under the assumption that the unknown matrix is incoherent and the subsample is drawn uniformly at random. Are these assumptions necessary? It is well known that Matrix Completion in its full generality is NP-hard. However, little is known if make additional assumptions such as incoherence and permit the algorithm to output a matrix of slightly higher rank. In this paper we prove that Matrix Completion remains computationally intractable even if the unknown matrix has rank $4$ but we are allowed to output any constant rank matrix, and even if additionally we assume that the unknown matrix is incoherent and are shown $90%$ of the entries. This result relies on the conjectured hardness of the $4$-Coloring problem. We also consider the positive semidefinite Matrix Completion problem. Here we show a similar hardness result under the standard assumption that $\mathrm{P}\ne \mathrm{NP}.$ Our results greatly narrow the gap between existing feasibility results and computational lower bounds. In particular, we believe that our results give the first complexity-theoretic justification for why distributional assumptions are needed beyond the incoherence assumption in order to obtain positive results. On the technical side, we contribute several new ideas on how to encode hard combinatorial problems in low-rank optimization problems. We hope that these techniques will be helpful in further understanding the computational limits of Matrix Completion and related problems.