On optimal distinguishers for Planted Clique

Ansh Nagda, Prasad Raghavendra · 2025

Read On optimal distinguishers for Planted Clique by Ansh Nagda, Prasad Raghavendra (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-01990.txt.

Introduction

How well can any fast algorithm sniff out a hidden clique in a random graph? A 2025 paper by Ansh Nagda and Prasad Raghavendra draws the exact line, assuming the standard hardness belief about the problem.

In the planted clique problem, a graph is either purely random or random with a dense knot of connections planted inside. A distinguisher's edge over coin flipping is its advantage. The authors show no efficient method can beat the best low-degree polynomial test, and that a simple edge count already reaches the ceiling. They also build planted distributions that are harder still. The work pins down, unusually precisely, what computation can and cannot see in this classic puzzle.

Catalog record

CREATORAnsh Nagda, Prasad Raghavendra
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE104 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-01990

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On optimal distinguishers for Planted Clique Ansh Nagda, Prasad Raghavendra Abstract 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 ) G(n,1/2) – the standard Erdős–Rényi model, or G ⁡ ( n , 1 / 2 , k ) G(n,1/2,k) – the Erdős–Rényi model with a clique planted on a random subset of k k vertices. The Planted Clique Hypothesis asserts that efficient algorithms cannot achieve advantage better than some absolute constant, say 1 / 4 1/4 , whenever k = n 1 / 2 − Ω ⁡ ( 1 ) 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 ) ) ⋅ k 2 / ( π ​ n ) (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 k -cliques such that no efficient algorithm can distinguish 𝒫 ∗ \mathcal{P}^{*} from G ⁡ ( n , 1 / 2 ) G(n,1/2) with advantage n − d n^{-d} for an arbitrarily large constant d d . In other words, there exist alternate planted distributions that are much harder than G ⁡ ( n , 1 / 2 , k ) 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. 1 Introduction In a distinguishing problem , one receives a sample drawn from one of two distributions, which we will refer to as the “planted” and “null” distributions. The task of the algorithm is to determine the source distribution. The archetypal example of a distinguishing problem is the Planted Clique problem. Here the null distribution \mathcal{N}=G(n,1/2) is the Erdős–Rényi model over n -vertex graphs, where each edge is included independently with probability \frac{1}{2} . The planted distribution \mathcal{P}=G(n,1/2,k) is parametrized by a number 0\leq k\leq n , and is sampled as follows. 1 1 1 This planted distribution has been referred to as the binomial k model [ HWX15 , BJ23 ] . See [ HS24 ] for a comparison with other models. • Sample a random subset S\subseteq[n] of vertices by including each vertex independently with probability \frac{k}{n} . • Generate an Erdős–Rényi random graph G\sim G(n,1/2) . • Plant a clique amongst the vertices in S . That is, set G_{ij}=1 for all i,j\in S . We will focus on the computationally hard regime where k=n^{1/2-\alpha} for some 0<\alpha<1/2 . In this regime, the Planted Clique problem is information theoretically easy, but has long been hypothesized to be intractable for polynomial-time algorithms [ Jer92 , Kuč95 , AKS98 , KV02 ] . The intractability of distinguishing problems is quantified in terms of the distinguishing advantage . Let A be a test , that is, a randomized mapping A from the set of n -vertex graphs to \{\pm 1\} . We will define the advantage achieved by A as \textup{Adv}^{(\mathcal{P},\mathcal{N})}(A):=|{\mathbb{E}}_{\mathcal{P}}[A]-{\mathbb{E}}_{\mathcal{N}}[A]|=2\cdot|\Pr_{x\sim\mathcal{P}}[A(x)=1]-\Pr_{x\sim\mathcal{N}}[A(x)=1]|\in[0,2]. Above, the expectation is taken over both x and the internal randomness of A . In this terminology, the Planted Clique Hypothesis can be stated as follows. Conjecture 1.1 . (Planted Clique Hypothesis) Let \alpha>0 and set k=n^{1/2-\alpha} . Let \mathcal{N}=G(n,1/2) and \mathcal{P}=G(n,1/2,k) . For every randomized polynomial time test A and all sufficiently large n , \textup{Adv}^{(\mathcal{P},\mathcal{N})}(A)\leq 1/4. In light of the seeming intractability of the Planted Clique problem, it is natural to ask the following question. What is the optimal (i.e., smallest) advantage achievable by any efficient algorithm? In an elegant sequence of works, Hirahara and Shimizu [ HS23 , HS24 ] demonstrated that random self-reductions can be used to amplify the hardness of the Planted Clique problem. In particular, these works showed that Conjecture 1.1 implies the following stronger bound on the advantage. Theorem 1.2 . (Theorem 1.3, (7) in [ HS24 ] ) Assume the Planted Clique Hypothesis. Let \alpha,\gamma>0 and set k=n^{1/2-\alpha} . Let \mathcal{N}=G(n,1/2) and \mathcal{P}=G(n,1/2,k) . For every randomized polynomial time test A , \textup{Adv}^{(\mathcal{P},\mathcal{N})}(A)=n^{\gamma}\cdot O\left(\frac{k^{2}}{n}\right). Notice that on average, graphs sampled from the planted distribution \mathcal{P} have \binom{k}{2}/2 more edges than an Erdős–Rényi graph sampled from \mathcal{N} , owing to the clique planted among k vertices. This slight mismatch in the expected number of edges can be used to efficiently distinguish the planted and null distributions with an advantage of \Omega\left(\frac{k^{2}}{n}\right) . Thus the above bound on the distinguishing advantage is correct up to an arbitrary polynomial factor in n . This leaves the question of whether we can characterize the optimal advantage for Planted Clique? Subsequently, one may ask which class of algorithms are optimal distinguishers for the problem? Conversely, can we construct alternate planted distributions where the optimal advantage is significantly smaller than \frac{k^{2}}{n} , say o(n^{-100}) ? This work make progress towards answering all these questions. In order to explain our results, we will first give an introduction to the low-degree method . Low-degree polynomials. Starting with the works of Hopkins and Steurer [ Hop18 , HS17 ] , the low-degree method has emerged as an effective heuristic to determine whether a distinguishing problem is computationally tractable or not. Roughly speaking, the low-degree method is based on the hypothesis that if all degree D polynomials fail on a distinguishing task, then all algorithms running in time 2^{D} fail too. To elucidate further, we will first set up some terminology on real-valued test functions. Fix a distinguishing problem between a planted distribution \mathcal{P} and a null distribution \mathcal{N} , both over a set \Omega . For a real-valued test function f:\Omega\to{\mathbb{R}} , let us define \textup{R}^{(\mathcal{P},\mathcal{N})}(f) as the ratio \textup{R}^{(\mathcal{P},\mathcal{N})}(f):=\frac{{\mathbb{E}}_{\mathcal{P}}[f]-{\mathbb{E}}_{\mathcal{N}}[f]}{\|f\|_{2,\mathcal{N}}}=\frac{{\mathbb{E}}_{\mathcal{P}}[f]-{\mathbb{E}}_{\mathcal{N}}[f]}{\sqrt{{\mathbb{E}}_{\mathcal{N}}[f^{2}]}}\in{\mathbb{R}}. Informally, one can think of \textup{R}^{(\mathcal{P},\mathcal{N})}(f) measuring the “performance” of f at distinguishing between \mathcal{P} and \mathcal{N} – note that if the output of f is in \{\pm 1\} , then one recovers the advantage |\textup{R}^{(\mathcal{P},\mathcal{N})}(f)|=\textup{Adv}^{(\mathcal{P},\mathcal{N})}(f). \textup{R}^{(\mathcal{P},\mathcal{N})}(f) is not as readily interpreted if the output of f is not restricted to \{\pm 1\} , but we will nevertheless treat it as a sort of distinguishing advantage. For a family of test functions \mathcal{F}\subseteq L^{2}(\mathcal{N}) , let \textup{R}^{(\mathcal{P},\mathcal{N})}[\mathcal{F}] denote the optimal advantage achieved by a function in \mathcal{F} , i.e., \textup{R}^{(\mathcal{P},\mathcal{N})}[\mathcal{F}]:=\sup_{f\in\mathcal{F}}\textup{R}^{(\mathcal{P},\mathcal{N})}(f). For simplicity, let us restrict our attention to the case where \Omega=\{\pm 1\}^{N} is the N -dimensional hypercube for some N\in{\mathbb{N}} . In our running example of Planted Clique, one should think of N=\binom{n}{2} ; a graph G will be

Read the complete text