FOCS Conference 2025 Conference Paper
- Ansh Nagda
- Prasad Raghavendra
In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a distinguishing algorithm is measured by its advantage, i. e. , its incremental probability of success over a random guess. A classic example of a distinguishing problem is the Planted Clique problem, where the input is a graph sampled from either $G(n, 1 / 2)$ - the standard Erdős-Rényi model, or $G(n, 1 / 2, k)$ the Erdős-Rényi model with a clique planted on a random subset of k vertices. The Planted Clique Hypothesis asserts that efficient algorithms cannot achieve advantage better than some absolute constant, say 1/4, whenever $k=n^{1 / 2-\Omega(1)}$. In this work, we aim to precisely understand the optimal distinguishing advantage achievable by efficient algorithms on Planted Clique. We show the following results under the Planted Clique hypothesis: •Optimality of low-degree polynomials: No efficient algorithm can beat the advantage the optimal low-degree polynomial. Concretely, this means that the advantage of any efficient algorithm is at most $(1+o(1)) \cdot k^{2} /(\sqrt{\pi} n)$, which is optimal in light of a simple edge-counting algorithm achieving this bound. •Harder planted distributions: There is an efficiently sampleable distribution ${\mathcal{P}}^{*}$ supported on graphs containing k cliques such that no efficient algorithm can distinguish ${\mathcal{P}}^{*}$ from $G(n, 1 / 2)$ with advantage $n^{-d}$ for an arbitrarily large constant d. In other words, there exist alternate planted distributions that are much harder than $G(n, 1 / 2, k)$. Along the way, we prove a constructive hard-core lemma for a broad class of distributions with respect to low-degree polynomials. This result is applicable much more widely beyond Planted Clique and might be of independent interest.