{"id":"30d420a5-281d-4360-afdd-a1b738f6c450","arxiv_id":"2505.01990","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under the Planted Clique Hypothesis, the optimal efficient distinguishing advantage for Planted Clique is (1+o(1))*k^2/(sqrt(pi)*n), and there exist planted distributions that are much harder to detect than the usual one.","lead":"This paper proves that, assuming the Planted Clique Hypothesis, no efficient algorithm can distinguish a graph with a hidden clique from a random graph better than the best low-degree polynomial test, which reduces to counting edges. It also constructs alternate planted distributions whose detection is far harder than for the standard planted clique.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Corollary 1.5's exact √π constant rests on an invalid application of Claim 7.4: p=f−E_N[f] has range [−2,2], not [−1,1]; the proof needs a normalization fix.","rationale":"The central reduction (Theorems 4.3 and 7.1) and the low-degree advantage calculation are sound in structure: the amplification via vertex resampling, the subspace projection, and the anticoncentration lemma are internally coherent, and the reliance on the Planted Clique Hypothesis is explicit and conditional rather than a correctness flaw. The cleanest genuine defect in the argument for the strongest claim is the Claim 7.4 application discussed above: it directly affects the exact constant in Corollary 1.5 and is not justified as written. The fix is short, which is why I do not move the verdict from the reader's CONDITIONAL; the paper should be revised to apply Claim 7.4 to f (or to an explicitly normalized p) before the headline bound is accepted. The reader's own flagged issue, the clique-size overclaim in Theorem 1.9, is also real: the proof constructs a clique of size roughly n^{1/2−10β} rather than n^{1/2−α}, so Theorem 1.9 should be corrected or restated. That issue is secondary because Theorem 1.5 does not depend on the exact clique size of the hard-core distribution. I also note the proof contains a smaller expository mismatch in the notation for the anticoncentration parameter (polynomial versus exponential in d), but since d is constant in the applications this does not affect the stated results. Overall, the paper's main conditional claim is plausible and largely well supported, but the exact-constant proof needs the normalization correction identified here.","tokens_in":30210,"tokens_out":28209,"duration_ms":267130,"concrete_test":"Re-derive Claim 7.4 for two candidate functions: p=f with range [−1,1], and q=(f−E_N[f])/2 with range [−1,1]. For q, Claim 7.4 gives ∥q_{=1}∥≤√(2/π), hence ∥(f−E_N[f])_{=1}∥≤2√(2/π); for p=f, it gives ∥(f−E_N[f])_{=1}∥≤√(2/π). Then recompute the last display of Corollary 1.5: only the p=f version yields the stated (1+o(1))k²/(√π·n). If the factor-2 version is instead obtained, Corollary 1.5 must be restated with 2k²/(√π·n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"Corollary 1.5 obtains its headline bound k²/(√π·n) by combining R(P,N)[F≤1]≈k²/(√2·n) with the bound Var_N(Π_{F≤1}f)^{1/2}≤√(2/π). The latter is derived by applying Claim 7.4 to p=f−E_N[f]. But Claim 7.4 assumes p:{±1}^T→[−1,1], and its proof uses |p|≤1 to bound |E[p·Σχ_i]|≤E|Σχ_i|. Since f=E[A]∈[−1,1], the function p=f−E_N[f] ranges over [−2,2], so the displayed inequality is not justified as written. This is not merely cosmetic: if the proof is read literally, the asymmetry forces a factor 2, yielding Var_N(Π_{F≤1}f)^{1/2}≤2√(2/π) and changing the final constant from k²/(√π·n) to 2k²/(√π·n). The conclusion is recoverable because subtracting the constant does not change degree-1 Fourier coefficients, so one can instead apply Claim 7.4 to p=f directly and obtain the intended √(2/π). But the text as written applies the claim to the wrong, unbounded-in-[-1,1] function, leaving the paper's central quantitative claim unproved until this normalization is corrected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the optimal distinguishing advantage for the Planted Clique problem under the Planted Clique Hypothesis. Its main results are: (1) no randomized polynomial-time test can beat the low-degree advantage for planted clique, stated quantitatively as Adv(P,N)(A) ≤ (1+o(1)) k^2/(√π n) for k = n^{1/2−Ω(1)}; (2) a constructive hard-core lemma that produces an efficiently sampleable distribution P* supported on graphs with large cliques that is indistinguishable from G(n,1/2) with advantage o(n^{-D}) for arbitrarily large constant D. The technical core is a general hardness-amplification theorem (Theorem 4.3) that upgrades a distinguisher for a noised planted distribution to a constant-advantage distinguisher for a harder planted distribution, together with a general hard-core lemma against a tractable subspace of distinguishers (Theorem 5.1). The Planted Clique results are obtained by instantiating these general theorems with low-degree polynomials and the permuted vertex-resampling Markov chain.","tokens_in":30463,"tokens_out":31802,"duration_ms":303863,"significance":"If the results are correct, this is a significant contribution to the average-case complexity of Planted Clique: it gives the first PCH-conditional tight characterization of the optimal distinguishing advantage up to 1+o(1) factors, and it provides a uniform hard-core distribution for Planted Clique, a type of result that is often difficult to obtain for uniform polynomial-time algorithms. The general framework of Theorem 4.3 and Theorem 5.1 is also potentially useful beyond the planted clique setting. The paper is careful to state which claims are conditional on the Planted Clique Hypothesis, and the reductions are explicit and detailed, with several technical lemmas proved in full. The main results are not unconditional, but the conditional statements are precise and the quantitative bounds are explicit.","major_comments":[{"comment":"The first displayed inequality in Lemma 2.1, ∥f∥_{1,N} ≥ ∥f∥_{3,N}^2/∥f∥_{4,N}^2, is false as stated. On a two-point uniform probability space, take f(1)=1 and f(2)=0. Then ∥f∥_{1,N}=1/2, ∥f∥_{3,N}^2/∥f∥_{4,N}^2 = (1/2)^{2/3}/(1/2)^{1/2} = 2^{-1/6} ≈ 0.891 > 1/2. Log-convexity of Lp norms gives ∥f∥_{3,N} ≤ ∥f∥_{1,N}^{1/9}∥f∥_{4,N}^{8/9}, equivalently ∥f∥_{1,N} ≥ ∥f∥_{3,N}^9/∥f∥_{4,N}^8, not the displayed bound. This false inequality is used in the proof of Claim 5.3 to assert ∥1+g∥_{1,P} ≥ (2c)^{-1}∥1+g∥_{2,N}. Furthermore, that asserted inequality is scale-inconsistent: the ratio ∥1+g∥_{3,N}^2/∥1+g∥_{4,N}^2 is invariant under multiplying 1+g by a constant, whereas ∥1+g∥_{2,N} scales linearly. The proof of Theorem 5.1, and therefore Theorems 1.8 and 1.9, does not go through as written. The argument may be repairable with a correct log-convexity inequality and adjusted constants, but the manuscript must be revised accordingly.","section":"§2, Lemma 2.1 and §5.1, Claim 5.3"},{"comment":"Claim 7.4 is applied to p = f − E_N[f], but f∈[−1,1] only implies p∈[−2,2], which violates the hypothesis |p|≤1 of Claim 7.4. The proof of Claim 7.4 uses |p|≤1 to bound |E[p·Σχ_i]| ≤ E|Σχ_i|; read literally, the asymmetric range forces an extra factor of 2, changing the final constant from k²/(√π n) to 2k²/(√π n). The intended result is recoverable by applying Claim 7.4 to f itself, because subtracting the constant E_N[f] does not change the degree-1 Fourier coefficients. The application in the proof should be corrected.","section":"§7.2, proof of Corollary 1.5 (and Claim 7.4)"},{"comment":"The proof should clarify the clique-size parameter. The proof sets β = 2α and defines P* = M_sym(P′), where P′ is a perturbation of P = G(n,1/2,n^{1/2−α}). Since the permuted vertex-resampling chain keeps each clique vertex with probability p = n^{α−β}, the typical clique in P* has size about n^{1/2−β} = n^{1/2−2α}, which is smaller than the clique size n^{1/2−α} promised in the theorem statement. The final paragraph refers to cliques of size n^{1/2−10β}; the relationship among α, β, and the claimed clique size needs to be stated and proved consistently.","section":"§7.3, proof of Theorem 1.9"}],"minor_comments":[{"comment":"The final advantage calculation contains a typo: it should be Pr_{x∼N}[B(x)=1], not Pr_{x∼N}[B(x)=−1]. The preceding bounds on the probability that B outputs +1 under N make the intended expression clear.","section":"§4.1, proof of Theorem 4.3"},{"comment":"In the LP constraints, the condition is written as 0<|V(S)|≤d, but for the low-degree space F≤d the relevant condition is 0<|S|≤d. The formal proof in Section 5 works with a general subspace V and is fine, but the informal LP formulation should be consistent with the Fourier-degree convention.","section":"§3.2, LP formulation"},{"comment":"The lifted distributions Ψ and Ψ′ are sometimes referred to as Φ and Φ′ in Observation 6.3 and the surrounding discussion; please unify the notation.","section":"§6, notation"},{"comment":"The abstract and introduction describe advantage as 'incremental probability of success over a random guess,' but the formal definition normalizes advantage to lie in [0,2]. Please make the normalization explicit in the abstract or in the leading definition to avoid confusion.","section":"§1, Introduction"}],"recommendation":"major_revision","confidential_remarks":"The false inequality in Lemma 2.1 is the most serious technical issue and affects the hard-core lemma and Theorem 1.9. The Claim 7.4 application is a local but load-bearing mistake in the headline constant. Both appear repairable, so I recommend major revision rather than rejection; the conceptual reductions are clear and likely sound after the fixes are made."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Three things you should know. First, this is a genuine advance: under the Planted Clique Hypothesis, the authors prove that no efficient test beats the low-degree edge-counting advantage, up to a (1+o(1)) factor, closing the polynomial gap left by Hirahara–Shimizu. Second, the general machinery, a reduction from a stronger distinguisher to a PCH violation and a constructive hard-core lemma for low-degree subspaces, is well built and likely reusable. Third, there are two repairable blemishes.\n\nThe first blemish is in the proof of Corollary 1.5. The text applies Claim 7.4 to p = f − E_N[f], but p can range over [−2,2] and Claim 7.4 needs a [−1,1]-valued function. The fix is trivial: apply the claim to f itself, which is [−1,1]-valued; the degree-1 Fourier coefficients do not change when you subtract a constant. So the headline constant k²/(√π n) survives, but the proof as written has a real gap.\n\nThe second blemish is Theorem 1.9's clique-size guarantee. The theorem states that P* is supported on graphs with a clique of size n^{1/2−α}, but the proof preserves roughly n^{1/2−10β} with β=2α, i.e. n^{1/2−20α}. This is an overclaim in the abstract and theorem statement; the fix is to restate with the smaller size or adjust parameters. It does not affect Theorems 1.4 and 1.5.\n\nThe new content is solid. The low-degree advantage calculation for planted clique is standard, the lifted-product analysis in Section 6 is technically impressive, and the general Theorems 4.3 and 5.1 are clearly stated with explicit conditions. The paper ships no code or formal proofs, but the mathematical arguments are detailed enough to check. The citation pattern is appropriate; the reliance on Hirahara–Shimizu's amplification is clearly credited.\n\nIf you work on planted clique or on the low-degree method, this is worth your time. It deserves a serious referee; I would accept it for peer review and ask for the two fixes above. I'd bring it to our reading group.","headline":"A solid, conditional result that closes the polynomial gap to the optimal planted-clique distinguishing advantage, with two easily repairable gaps in the written proofs.","tokens_in":31057,"tokens_out":4224,"would_cite":true,"duration_ms":41416,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q25","05C80","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that, assuming the Planted Clique Hypothesis, edge counting is the optimal polynomial-time distinguisher for planted cliques, and it constructs planted distributions that are far harder to distinguish.","keywords":["planted clique","distinguishing advantage","low-degree method","hard-core distribution","hardness amplification","average-case complexity","anticoncentration","random graph theory"],"falsifier":"Exhibit a randomized polynomial-time test that provably distinguishes $G(n,1/2,n^{1/2-\\alpha})$ from $G(n,1/2)$ with advantage larger than $(1+\\varepsilon) k^2/(\\sqrt{\\pi} n)$ for some fixed $\\alpha>0$ and $\\varepsilon>0$; that would refute the tight bound. A test with constant advantage at $k=n^{1/2-\\Omega(1)}$ would instead refute the underlying Planted Clique Hypothesis.","tokens_in":29968,"feed_emoji":"🕸️","tokens_out":10806,"duration_ms":104962,"temperature":0.7,"pith_summary":"Planted Clique detection asks how well any efficient test can tell a random graph $G(n,1/2)$ from one with a planted clique of size $k=n^{1/2-\\alpha}$. This paper proves that, assuming the Planted Clique Hypothesis, no randomized polynomial-time test has distinguishing advantage larger than $(1+o(1)) k^2/(\\sqrt{\\pi} n)$ — the advantage already achieved by edge counting. The same low-degree optimality holds for mildly perturbed planted distributions. The paper also constructs an efficiently sampleable hard-core planted distribution, still supported on graphs with $k$-cliques, that no efficient test can tell from $G(n,1/2)$ with advantage $n^{-D}$ for an arbitrarily large constant $D$. The route passes through a general hardness-amplification theorem and a constructive hard-core lemma against low-degree polynomials.","feed_headline":"Edge counting is optimal for hidden cliques","feed_subtitle":"If the Planted Clique Hypothesis holds, edge counting is optimal—and harder planted distributions exist.","key_machinery":"The central object is the permuted vertex-resampling Markov chain $M_{\\mathrm{sym}}$: pick a random vertex permutation, then resample each vertex's incident edges with probability $1-p$. Its noise operator $T$ has Fourier eigenfunctions $\\chi_S$ with eigenvalue $p^{|V(S)|}$, so low-degree polynomials contain the top eigenspace. This lets the reduction write a test $f=f_+ + f_-$ with $f_+$ low-degree; $T$ contracts $f_-$ by $p^{2\\sqrt{d}}$, and the remaining signal is amplified into a constant-advantage test. The second load-bearing object is a constructive hard-core lemma: acceptance probabilities $p(x)=\\sigma'(1+g(x))$ are computed from a smoothed soft-threshold $\\sigma$ and an optimizer $g$ over a tractable subspace, making low-degree moments of the new distribution vanish while keeping $\\|dP^*/dP\\|_\\infty \\le 1+o(1)$. The proof relies on hypercontractivity of the subspace and on anticoncentration of noise-resistant functions under the planted measure.","core_discovery":"The central claim is that the Planted Clique Hypothesis forces the optimal efficient distinguishing advantage to coincide with the low-degree advantage. For every constant degree $d$ and every randomized polynomial-time test $A$, $\\mathrm{Adv}(P,N)(A) \\le (1+o_n(1)) R(P,N)[\\mathcal{F}_{\\le d}]$, and since the low-degree advantage for $P=G(n,1/2,k)$ is $(1+o(1))k^2/(\\sqrt{2}n)$, the edge-counting test achieves the optimal constant $k^2/(\\sqrt{\\pi} n)$. The proof splits a hypothetical distinguisher into low- and high-degree parts, applies a vertex-resampling noise operator whose spectral gap crushes the high-degree part, amplifies the residual, and rounds by an anticoncentration lemma for noise-resistant functions. A second thread solves a smoothed linear-programming dual to build a distribution $P'$ whose low-degree advantage is at most $\\delta$ while its density relative to $P$ stays $1+o(1)$; feeding this into the perturbation theorem yields the hard-core distribution with advantage $o(n^{-D})$.","pith_inferences":["Because the hard-core distribution is contiguous with the standard planted distribution yet has advantage $o(n^{-D})$, it is a natural substrate for cryptography from planted graphs: the clique can remain as a witness while the distinguishing signal is erased.","The amplification template—project onto the high-degree complement of a noise operator with known spectral gap and round via anticoncentration—should transfer to other sparse-signal distinguishing problems over the hypercube, such as planted dense subgraphs or spiked tensor models.","The LP-dual plus stochastic-gradient-descent construction suggests that the real bottleneck in such reductions is not low-degree hardness itself but the existence of a tractable subspace containing the top eigenspace.","A direct next step would be to instantiate the general theorems on neighboring problems and compute the corresponding optimal constants, predicting edge-counting-style optimality under the analogous hardness hypotheses."],"forward_implications":["If the Planted Clique Hypothesis is true, no polynomial-time test can outperform edge counting in the $k=n^{1/2-\\alpha}$ regime by more than a $1+o(1)$ factor.","Low-degree polynomials are not just a heuristic benchmark for planted clique: under the same hypothesis they are provably optimal among all efficient tests.","There are efficiently sampleable distributions that contain a clique of size $n^{1/2-\\alpha}$ yet are indistinguishable from $G(n,1/2)$ by any polynomial-time test up to advantage $o(n^{-D})$.","The perturbation theorem makes low-degree optimality stable: adding a bounded-density perturbation and a small amount of noise to the planted distribution cannot create an efficient distinguisher beyond the low-degree advantage.","The hard-core lemma is generic: whenever a tractable hypercontractive subspace has vanishing advantage on a pair of distributions, a nearby perturbation with subspace advantage $n^{-d}$ can be found efficiently."],"supporting_citations":[{"why":"Supplies the hardness-amplification bound $\\mathrm{Adv} \\le n^{\\gamma}O(k^2/n)$ that converts constant advantage into the polynomial-factor starting point the paper tightens to $1+o(1)$.","marker":"[HS24]"},{"why":"Supplies the expression $R(P,N)[\\mathcal{F}_{\\le d}]^2 = \\sum_{|S|\\le d}(k/n)^{2|V(S)|}$ used to fix the optimal constant.","marker":"[Hop18]"},{"why":"Supplies the global hypercontractivity bound for symmetric low-degree functions on the p-biased hypercube used in the anticoncentration proof.","marker":"[Kee+21]"},{"why":"Supplies Bonami's fourth-moment lemma for degree-$d$ hypercube polynomials, used to verify the hypercontractivity conditions.","marker":"[Bon70]"},{"why":"Supplies the stochastic-gradient-descent convergence theorem used to solve the smoothed dual program and construct the hard-core distribution efficiently.","marker":"[GG23]"}],"fun_headline_variants":["Edge counting achieves optimal hidden clique detection","Low-degree polynomials are optimal for Planted Clique","Harder planted distributions exist under PCH","Optimal hidden clique advantage is edge counting","Planted Clique: edge counting matches the optimum"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole characterization is conditional on the unproven Planted Clique Hypothesis—that no polynomial-time test can distinguish a graph with a planted clique of size $k=n^{1/2-\\Omega(1)}$ from $G(n,1/2)$ with constant advantage—and on the technical niceness conditions (tractability, hypercontractivity, and anticoncentration) holding for the planted clique instantiation.","fun_headline_variants_meta":{"raw":{"variants":["Edge counting achieves optimal hidden clique detection","Low-degree polynomials are optimal for Planted Clique","Harder planted distributions exist under PCH","Optimal hidden clique advantage is edge counting","Planted Clique: edge counting matches the optimum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000625,"raw_usage":{"total_tokens":3003,"prompt_tokens":1167,"completion_tokens":1836,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":783,"completion_tokens_details":{"reasoning_tokens":1767}},"tokens_in":783,"tokens_out":1836,"duration_ms":17697,"temperature":1.0,"reasoning_tokens":1767,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T04:06:17.597196+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Exhibit a randomized polynomial-time test that provably distinguishes $G(n,1/2,n^{1/2-\\alpha})$ from $G(n,1/2)$ with advantage larger than $(1+\\varepsilon) k^2/(\\sqrt{\\pi} n)$ for some fixed $\\alpha>0$ and $\\varepsilon>0$; that would refute the tight bound. A test with constant advantage at $k=n^{1/2-\\Omega(1)}$ would instead refute the underlying Planted Clique Hypothesis.","supporting_citations":[],"review_version":1}