On optimal distinguishers for Planted Clique

Ansh Nagda; Prasad Raghavendra

REVIEW 3 major objections 4 minor 1 cited by

On optimal distinguishers for Planted Clique

T0 review · 3 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2505.01990 v2 pith:LTMWV5RZ submitted 2025-05-04 cs.CC cs.DS

Ansh Nagda , Prasad Raghavendra This is my paper · ORCID

classification cs.CCcs.DS MSC 68Q1768Q2505C8060C05

keywords plantedcliquedistinguishingadvantagelow-degreemethodhard-coredistributionhardnessamplificationaverage-casecomplexityanticoncentrationrandomgraphtheory

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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})$.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

The 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.

If 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[§2, Lemma 2.1 and §5.1, Claim 5.3] 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.
[§7.2, proof of Corollary 1.5 (and Claim 7.4)] 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.
[§7.3, proof of Theorem 1.9] 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.

minor comments (4)

[§4.1, proof of Theorem 4.3] 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.
[§3.2, LP formulation] 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.
[§6, notation] The lifted distributions Ψ and Ψ′ are sometimes referred to as Φ and Φ′ in Observation 6.3 and the surrounding discussion; please unify the notation.
[§1, Introduction] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; all main claims are conditional reductions from PCH with independent input calculations.

full rationale

The paper's central results are conditional statements: under the Planted Clique Hypothesis (Conjecture 1.1), it proves that no efficient distinguisher beats the low-degree advantage. The proof reduces a hypothetical stronger distinguisher to a constant advantage against the standard planted clique distribution, which would contradict PCH via the independent Hirahara–Shimizu amplification theorem [HS24]. This is a standard contrapositive reduction, not an assumption of the conclusion. The low-degree advantage R(P,N)[F≤d] is computed explicitly from the known Fourier expression (Appendix C, Claim 7.3), which is an independent calculation and not fitted from the target algorithm's advantage. The hard-core construction in Theorem 5.1 solves a linear/convex program whose optimality is bounded using mild hardness against V⊙4; the resulting distribution P* is defined by that construction, so its low-degree hardness is a property engineered by the construction rather than a renamed input. No uniqueness theorem is imported from the authors' own prior work, and no fitted parameter is relabeled as a prediction. The only notable issue is a technical normalization gap in the proof of Corollary 1.5: Claim 7.4 is stated for functions p:{±1}^T→[−1,1], but the proof applies it to p=f−E_N[f], which can have range [−2,2]. This is a correctness/verification issue in the constant calculation, not circularity: the intended bound is recoverable by applying Claim 7.4 directly to f (which does have range [−1,1]), and no part of the argument defines its target quantity in terms of itself. Self-citations appear only in context; the load-bearing cited result [HS24] is by different authors and supplies an independent hardness-amplification theorem.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central results are conditional on the Planted Clique Hypothesis; the proof also relies on standard analysis tools and on the equivalence between planted clique variants. No free parameters are fitted to data, and no new physical entities are introduced.

assumptions (3)

domain assumption Planted Clique Hypothesis (Conjecture 1.1): randomized polynomial-time tests have distinguishing advantage at most 1/4 for Planted Clique with k = n^(1/2-Omega(1)).
Used as the base hardness assumption for Theorems 1.4, 1.7, and 1.9. If PCH fails, the main results do not follow. Stated in Section 1, Conjecture 1.1.
domain assumption General theorems assume mild hardness of P against the subspace V (e.g., R(P,N)[V^4] <= 1/(8c)) and hypercontractivity, tractability, and anticoncentration conditions.
Theorem 5.1 assumes R(P,N)[V^4] <= 1/(8c); Theorem 4.3 assumes sampleability, tractability, and anticoncentration conditions. These are not proven in full generality but are verified for the planted clique instantiations.
domain assumption Equivalence of the binomial-k planted clique model with the standard uniform planted clique model (from [HS24]).
The paper uses the binomial model where each vertex is in the clique independently with probability k/n; standard PCH is often stated for a uniformly random k-subset. The paper cites [HS24] for equivalence but relies on it as a premise.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On optimal distinguishers for Planted Clique." pith.science (2026). https://pith.science/paper/LTMWV5RZ

@misc{pith2026250501990,
  author       = {Pith},
  title        = {Pith review of: On optimal distinguishers for Planted Clique},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LTMWV5RZ}},
  note         = {Machine review of arXiv:2505.01990}
}

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)$ -- the standard Erd\H{o}s-R\'{e}nyi model, or $G(n,1/2,k)$ -- the Erd\H{o}s-R\'{e}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: 1. 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. 2. 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
math.ST 2025-06 accept novelty 2.0 of 10

A survey of the low-degree polynomial framework for predicting statistical-computational gaps, covering definitions, evidence, connections to other methods, and open problems.

Reference graph

Works this paper leans on

8 extracted references · 3 canonical work pages · cited by 1 Pith paper

[1]

Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

[Abr+23] Damiano Abram, Amos Beimel, Yuval Ishai, et al. “Cryptography from planted graphs: security with logarithmic-size messages”. In:Theory of Cryptography Conference. Springer. 2023, pp. 286–315 (cit. on pp. 4, 5). 28 [ABW10] Benny Applebaum, Boaz Barak, and Avi Wigderson. “Public-key cryptography from different assumptions”. In: Proceedings of the f...

work page Pith review arXiv 1998
[2]

Complexity theoretic lower bounds for sparse principal component detection

1970, pp. 335–402 (cit. on p. 8). [BR13a] Quentin Berthet and Philippe Rigollet. “Complexity theoretic lower bounds for sparse principal component detection”. In: Conference on Learning Theory . 2013, pp. 1046– 1066 (cit. on p. 5). [BR13b] Quentin Berthet and Philippe Rigollet. “Complexity theoretic lower bounds for sparse principal component detection”. ...

arXiv 2020
[4]

Subexponential-time algo- rithms for sparse PCA

arXiv: 1801.00518 [math.ST] (cit. on p. 5). [Din+23] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, et al. “Subexponential-time algo- rithms for sparse PCA”. In: Foundations of Computational Mathematics (2023), pp. 1–50 (cit. on p. 5). [Din+25] Jingqiu Ding, Yiding Hua, Lucas Slot, et al. “Low degree conjecture implies sharp computational thresholds in st...

arXiv 2023
[10]

Large cliques elude the Metropolis process

1109/SFCS.1995.492584 (cit. on pp. 4, 6). [Jer92] Mark Jerrum. “Large cliques elude the Metropolis process”. In: Random Structures & Algorithms 3.4 (1992), pp. 347–359 (cit. on pp. 1, 5). [JP00] Ari Juels and Marcus Peinado. “Hiding cliques for cryptographic security”. In: De- signs, Codes and Cryptography 20.3 (2000), pp. 269–280 (cit. on p. 5). [Kee+21]...

arXiv 1992
[1982]

Tensor SVD: Statistical and computational limits

IEEE. 1982, pp. 80–91 (cit. on p. 6). [ZX18] Anru Zhang and Dong Xia. “Tensor SVD: Statistical and computational limits”. In: IEEE Transactions on Information Theory 64.11 (2018), pp. 7311–7338 (cit. on p. 5). A Proof of Claim 4.4 In this section we present the proof of Claim 4.4. Recall that our goal is to approximate Tf−(x), wheref(x) = EA[A(x)] is the ...

work page 2018
[2018]

The uniform hardcore lemma via ap- proximate bregman projections

2018, pp. 48–166. URL: http://proceedings.mlr.press/v75/brennan18a.html (cit. on p. 5). [BHK09] Boaz Barak, Moritz Hardt, and Satyen Kale. “The uniform hardcore lemma via ap- proximate bregman projections”. In: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms. SIAM. 2009, pp. 1193–1200 (cit. on p. 6). [BJ23] Guy Bresler and Ti...

arXiv 2019
[2019]

Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$

arXiv: 1911.01411 [cs.CC] (cit. on p. 5). [MW15] Zongming Ma and Yihong Wu. “COMPUTATIONAL BARRIERS IN MINIMAX SUB- MATRIX DETECTION”. In:The Annals of Statistics (2015), pp. 1089–1116 (cit. on p. 5). [MW23] Ankur Moitra and Alexander S. Wein. Precise Error Rates for Computationally Efficient Testing

work page Pith review arXiv 2015
[2023]

Average-case hardness of RIP cer- tification

arXiv: 2311.00289 [math.ST] . URL: https://arxiv.org/abs/ 2311.00289 (cit. on p. 5). [WBP16] Tengyao Wang, Quentin Berthet, and Yaniv Plan. “Average-case hardness of RIP cer- tification”. In: Advances in Neural Information Processing Systems29 (2016) (cit. on p. 5). [WBS16] Tengyao Wang, Quentin Berthet, and Richard J. Samworth. “STATISTICAL AND COMPUTATI...

arXiv 2016

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [1]

Average-Case Lower Bounds for Learning Sparse Mixtures, Robust Estimation and Semirandom Adversaries

[Abr+23] Damiano Abram, Amos Beimel, Yuval Ishai, et al. “Cryptography from planted graphs: security with logarithmic-size messages”. In:Theory of Cryptography Conference. Springer. 2023, pp. 286–315 (cit. on pp. 4, 5). 28 [ABW10] Benny Applebaum, Boaz Barak, and Avi Wigderson. “Public-key cryptography from different assumptions”. In: Proceedings of the f...

work page Pith review arXiv 1998

[2] [2]

Complexity theoretic lower bounds for sparse principal component detection

1970, pp. 335–402 (cit. on p. 8). [BR13a] Quentin Berthet and Philippe Rigollet. “Complexity theoretic lower bounds for sparse principal component detection”. In: Conference on Learning Theory . 2013, pp. 1046– 1066 (cit. on p. 5). [BR13b] Quentin Berthet and Philippe Rigollet. “Complexity theoretic lower bounds for sparse principal component detection”. ...

arXiv 2020

[3] [4]

Subexponential-time algo- rithms for sparse PCA

arXiv: 1801.00518 [math.ST] (cit. on p. 5). [Din+23] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, et al. “Subexponential-time algo- rithms for sparse PCA”. In: Foundations of Computational Mathematics (2023), pp. 1–50 (cit. on p. 5). [Din+25] Jingqiu Ding, Yiding Hua, Lucas Slot, et al. “Low degree conjecture implies sharp computational thresholds in st...

arXiv 2023

[4] [10]

Large cliques elude the Metropolis process

1109/SFCS.1995.492584 (cit. on pp. 4, 6). [Jer92] Mark Jerrum. “Large cliques elude the Metropolis process”. In: Random Structures & Algorithms 3.4 (1992), pp. 347–359 (cit. on pp. 1, 5). [JP00] Ari Juels and Marcus Peinado. “Hiding cliques for cryptographic security”. In: De- signs, Codes and Cryptography 20.3 (2000), pp. 269–280 (cit. on p. 5). [Kee+21]...

arXiv 1992

[5] [1982]

Tensor SVD: Statistical and computational limits

IEEE. 1982, pp. 80–91 (cit. on p. 6). [ZX18] Anru Zhang and Dong Xia. “Tensor SVD: Statistical and computational limits”. In: IEEE Transactions on Information Theory 64.11 (2018), pp. 7311–7338 (cit. on p. 5). A Proof of Claim 4.4 In this section we present the proof of Claim 4.4. Recall that our goal is to approximate Tf−(x), wheref(x) = EA[A(x)] is the ...

work page 2018

[6] [2018]

The uniform hardcore lemma via ap- proximate bregman projections

2018, pp. 48–166. URL: http://proceedings.mlr.press/v75/brennan18a.html (cit. on p. 5). [BHK09] Boaz Barak, Moritz Hardt, and Satyen Kale. “The uniform hardcore lemma via ap- proximate bregman projections”. In: Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms. SIAM. 2009, pp. 1193–1200 (cit. on p. 6). [BJ23] Guy Bresler and Ti...

arXiv 2019

[7] [2019]

Lifting Sum-of-Squares Lower Bounds: Degree-$2$ to Degree-$4$

arXiv: 1911.01411 [cs.CC] (cit. on p. 5). [MW15] Zongming Ma and Yihong Wu. “COMPUTATIONAL BARRIERS IN MINIMAX SUB- MATRIX DETECTION”. In:The Annals of Statistics (2015), pp. 1089–1116 (cit. on p. 5). [MW23] Ankur Moitra and Alexander S. Wein. Precise Error Rates for Computationally Efficient Testing

work page Pith review arXiv 2015

[8] [2023]

Average-case hardness of RIP cer- tification

arXiv: 2311.00289 [math.ST] . URL: https://arxiv.org/abs/ 2311.00289 (cit. on p. 5). [WBP16] Tengyao Wang, Quentin Berthet, and Yaniv Plan. “Average-case hardness of RIP cer- tification”. In: Advances in Neural Information Processing Systems29 (2016) (cit. on p. 5). [WBS16] Tengyao Wang, Quentin Berthet, and Richard J. Samworth. “STATISTICAL AND COMPUTATI...

arXiv 2016