Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

1 Introduction

• Average-case reductions must map natural instance distributions without destroying planted signals, and this difficulty leaves reductions between apparently equivalent decision problems unresolved.Existing lower bounds can also miss canonical generative models assumed by algorithmic results.Source: §1 · pp. 4–5

1.1 Overview

• The paper gives new lower bounds for planted independent set, general planted dense subgraph with deterministic community size, biased sparse PCA, and the subgraph stochastic block model.For planted dense subgraph, the bounds cover q = ˜Θ(n^-α) and p − q = ˜Θ(n^-γ), γ ≥ α; the subgraph stochastic block model is harder to detect than planted dense subgraph when k ≫ √n.Source: §1.1 · pp. 5–6
• Gaussian biclustering hardness applies to detecting a uniformly random flat k × k planted submatrix with equal entries, while sparse spiked Wigner has a different threshold when k ≫ √n.The biclustering reduction matches the barriers in for a composite-hypothesis variant.Source: §1.1 · p. 6
• The paper establishes tight lower bounds for sparse spiked Wigner and sparse PCA when k ≫ √n, including the first tight sparse PCA barrier across an entire parameter regime.For sparse PCA, it also gives an alternate reduction recovering prior lower bounds in the canonical simple-hypothesis-testing variant.Source: §1.1 · p. 6
• Distributional lifting, rejection kernels, reflection cloning, and random rotations provide reduction techniques that preserve planted structure while mapping problems approximately in total variation.Poisson and Gaussian lifting yield different parameter scalings; reflection cloning supports sharper bounds for sparse spiked Wigner and sparse PCA, and random rotations connect sparse spiked Wigner to spiked-covariance sparse PCA.Source: §1.1 · p. 7

1.2 Hardness Results from an Algorithmic Perspective

• Problems admitting a sum test—including biased sparse PCA, planted independent set, planted dense subgraph, and biclustering—show different detection and recovery gaps from problems without one.The first group loses its statistical-computational gap around k = Θ(n^2/3) and has a detection-recovery gap for k ≫ √n; rank-1 submatrix, the subgraph stochastic block model, and sparse PCA retain their gap across sparsities and have no detection-recovery gap in the stated setting.Source: §1.2 · p. 9

1.3 Prior Work

• The paper strengthens planted dense subgraph lower bounds to deterministic community size and all p > q with p − q = O(q), and establishes computational-statistical gaps for the introduced subgraph stochastic block model.The latter contrasts with the two-community stochastic block model, which has no such gaps for partial or exact recovery in the cited regimes.Source: §1.3 · p. 10
• Earlier planted-clique reductions cover sparse PCA and other average-case problems, while prior sparse PCA lower bounds do not match conjectured algorithmic upper bounds when k differs polynomially from √n.Prior work also established SOS lower bounds for sparse spiked Wigner matching planted-clique reductions.Source: §1.3 · pp. 10–11
• Prior lower bounds address restricted algorithms and computational models, including spectral methods, semidefinite and sum-of-squares relaxations, statistical queries, and regular resolution.The cited work also introduces a low-degree-polynomial, SDP, and tensor-decomposition meta-algorithm for Bayesian estimation with a matching lower bound for that meta-algorithm on the k-block stochastic block model.Source: §1.3 · p. 12

1.4 Notation

• The notation section defines distributional conventions, divergences, sparse-vector and graph notation, and asymptotic comparisons including ≫, ˜Θ, and ≲.It also specifies conventions for normal and beta distributions, the chi-squared distribution, and standard graph and indicator notation.Source: §1.4 · p. 12

2.1 Detection and Recovery Problems

• Detection reductions preserve asymptotic Type I+II error exactly, while recovery reductions preserve partial, weak, and exact recovery together.For the problems considered, the polynomial orders of computational and statistical barriers for the recovery variants generally differ only by sub-polynomial factors.Source: §2.1 · pp. 13–14

2.2 Problem Formulations

• For planted dense subgraph, results show a tight detection threshold of n²/k⁴ given the planted clique conjecture, while the passage states q(1−q) of a PDS instance is tight for recovery.Source: §2.2 · p. 15

Subgraph Stochastic Block Model.

• The subgraph stochastic block model is designed so edge-thresholding cannot solve detection, while biased sparse PCA restricts the planted vector to have an overall positive or negative bias.Source: Subgraph Stochastic Block Model · pp. 15, 17

2.3 Our Results

• Under the planted clique and planted-dense-subgraph recovery conjectures, Theorem 2.1 classifies easy, hard, and impossible regimes for the formulated problems (Figure 5).The classification is stated for problems in Section 2.2.Source: §2.3 · p. 17, Figure 5 · p. 19
• The paper develops lifting, rejection-kernel, reflection-cloning, and random-rotation reductions, then establishes algorithmic upper bounds and information-theoretic lower bounds.The reductions connect planted clique or planted dense subgraph recovery to the stated intermediate problems and sparse PCA variants.Source: §2.3 · p. 20
• The regime characterization remains incomplete for sparse PCA and biased sparse PCA; it omits SSBM recovery and treats only weak recovery for both PCA variants.Gaps remain for sparse PCA when k ≪ √n and biased sparse PCA detection when k ≫ √n; matching information-theoretic bounds and algorithms for the recovery variants remain open.Source: §2.3 · p. 20
• The stated sparse PCA and BSPCA hardness implications are depicted for d = Θ(n); the authors say their results extend mildly beyond this regime, but not tightly.They note that d = Θ(n) or d = Ω(n) is common in sparse PCA lower bounds, including prior reductions and sum-of-squares lower bounds.Source: §2.3 · p. 20

Distributional Lifting.

• Gaussian and Poisson distributional lifting iteratively doubles sparse-structure size while maintaining signal and independent noise, enabling planted-clique reductions across a wide range of parameter regimes.The approach replaces binary edge indicators with Gaussian or Poisson variables and uses distributional tricks such as Poisson splitting and Gaussian rotational invariance.Source: Distributional Lifting · pp. 20–21

Rejection Kernels.

• Rejection sampling approximately maps Bern(p) and Bern(q) samples to target distributions P and Q, enabling two changes of measure simultaneously in distributional lifting.The method thresholds samples from P′ and Q′ before mapping the resulting Bernoulli variables to P and Q.Source: Rejection Kernels · p. 21
• Reflection cloning for rank-1 submatrix detection introduces less randomness than distributional lifting, doubles both signal-vector sparsities with a mild signal decrease, and preserves independent Gaussian noise.Negating parts of the signal also precludes success by a sum test.Source: Rejection Kernels · p. 21
• Random rotations yield sparse PCA lower bounds matching and; using reflection cloning as an intermediate gives the first tight computational lower bound over k ≫ √n.The authors describe this as tight over an entire parameter regime and note the utility of natural average-case problems as reduction intermediates.Source: Rejection Kernels · p. 21

• A polynomial-time map that makes target-instance distributions close in total variation transfers a test for P′ to P with error at most ε + δ.Source: §3 · p. 22
• For composite alternatives, the second total-variation condition ensures each distribution in H1 is close to a prior mixture over the target alternative.Source: §3 · pp. 22–23
• In multi-step reductions, triangle inequality and data processing track how total-variation error accumulates across steps.Source: §3 · p. 23

4.1 Detecting Planted Generalized Diagonals

• For the random permutation argument, the number of fixed points has moments bounded by those of a rate-1 Poisson variable.Source: §4.1 · p. 24

4.2 Planted Clique Lifting

• Each PC-Lifting iteration approximately maps PC(n, k, p) to PC(2n, 2k, p^(1/4)), enabling larger planted cliques at higher edge density.Source: §4.2 · p. 25
• For q = ˜Θ(N^-α) and K = ˜Θ(N^β), randomized polynomial-time tests for PISD have asymptotic Type I+II error at least 1 under the PC conjecture.Source: §4.2 · p. 27

5.1 Rejection Kernels

• A rejection kernel is a randomized map that approximately sends Bern(p) and Bern(q) to arbitrary target distributions fX and gX, respectively.The general method applies entry-wise to planted-clique edge indicators, mapping planted edges to fX and other edges to gX.Source: §5.1 · pp. 28–29
• O_n(n^-3) total-variation error is achieved for both planted-clique-to-Poisson mappings under the stated conditions.The maps send 1 to Pois(cλ) and Bern(q) to Pois(λ), and can be computed in O(log n) time.Source: §5.1 · p. 32

Then the map

• O_n(n^-3) total-variation error is achieved when mapping Bern(p) to N(μ, 1) and Bern(q) to N(0, 1).The polynomial-time Gaussian map is used in reductions involving Gaussian observations and Gaussian-entry random matrices.Source: Then the map · p. 33

5.2 Distributional Lifting

• The procedure generalizes PC-Lifting to distributions with natural cloning maps and, after ℓ iterations, produces a planted submatrix of size 2^ℓk × 2^ℓk in a matrix of size 2^ℓn × 2^ℓn.The Gaussian and Poisson families used in the paper have natural cloning maps; thresholding converts the lifted entries into graph edge indicators.Source: §5.2 · p. 33
• Distributional lifting uses rejection kernels, entry-wise cloning, random permutation, and thresholding to transform planted instances into larger planted-subgraph instances.Cloning doubles the matrix dimension and planted-subgraph size at each iteration; random permutation handles the anti-diagonal entries approximately in total variation.Source: §5.2 · pp. 33–34
• Intermediate distributions with natural cloning maps enable parameter tradeoffs for tight planted-dense-subgraph lower bounds that graph-only cloning maps cannot achieve.The construction front-loads total-variation loss in the initial rejection-kernel mapping rather than incurring entry-wise loss during cloning.Source: §5.2 · p. 34
• Thresholding W entrywise at t maps the planted matrix model to G(2^ℓn, 2^ℓk, p, q) and the null model to G(2^ℓn, q).Here p = P_X∼P_λℓ[X > t] and q = P_X∼Q_λℓ[X > t].Source: §5.2 · p. 38
• Combining the total variation bounds with the data processing inequality proves the distributional lifting theorem.Source: §5.2 · p. 38

6.1 Poisson Lifting and Lower Bounds for Low-Density PDS

• Poisson lifting reduces planted clique to low-density PDS and strengthens prior lower bounds to fixed planted size k.The regime has p = cq for fixed c > 1 and q = ˜Θ(n^-α); the reduction applies when p/q approaches c as well as when p = cq exactly.Source: §6.1 · pp. 38, 39, 41
• For q = ˜Θ(N^-α) and K = ˜Θ(N^β), polynomial-time tests have asymptotic Type I+II error at least 1 under the planted clique conjecture.The lower bound holds for the theorem’s stated parameter sequence and fixed planted clique density p ≤ 1/2.Source: §6.1 · p. 40

6.2 Gaussian Lifting and Lower Bounds for High-Density PDS and BC

• Gaussian lifting establishes a planted-clique-based lower bound for high-density PDS when q = Θ(1), p − q = ˜Θ(N^-α), and K = ˜Θ(N^β).For the theorem’s stated parameter sequence, polynomial-time tests have asymptotic Type I+II error at least 1 assuming the planted clique conjecture at density 1/2.Source: §6.2 · pp. 41, 43
• Gaussian lifting reduces planted clique to biclustering and gives tight computational lower bounds for simple-vs-simple testing, strengthening earlier BC lower bounds.For μ = ˜Θ(N^-α) and K = ˜Θ(N^β), polynomial-time tests have asymptotic Type I+II error at least 1 under the planted clique conjecture at density 1/2.Source: §6.2 · pp. 41, 44
• For biclustering recovery, the stated boundary β*=1/2 implies recovery is conjectured harder than detection when β > 1/2, with exact-recovery impossibility under PDS and planted clique recovery assumptions.The theorem’s recovery result rules out polynomial-time recovery with success probability bounded below by a positive constant under the stated assumptions.Source: §6.2 · pp. 45–46
• For the stated high-density PDS and BC parameters, Gaussian lifting rules out polynomial-time recovery under the PDS recovery conjecture.The reduction transfers the planted support, and a recovery procedure would yield a planted-clique distinguisher contradicting the conjecture.Source: §6.2 · pp. 46–47
• The same reduction implies hardness for partial and weak recovery if the PDS conjecture is strengthened to cover those recovery tasks.BC-Recovery exactly preserves the latent support when mapping PDS recovery instances to BC recovery instances.Source: §6.2 · p. 47

6.3 Lower Bounds for General PDS

• The general-regime lower bound uses a reduction combining Gaussian-Lifting and Poisson-Lifting, whose correctness follows from the lifting and rejection-kernel guarantees.The authors use this reduction to identify the computational barrier for general PDS.Source: §6.3 · pp. 47–48
• Under the planted clique conjecture, polynomial-time tests have asymptotic Type I+II error at least 1 for the stated general PDS parameter sequences.The theorem’s regime includes p−q=˜Θ(N^-γ), q=˜Θ(N^-α), K=˜Θ(N^β), with γ≥α.Source: §6.3 · p. 48

7.1 Reflecting Cloning and Rank-1 Submatrix

• Reflection cloning uses only random row and column permutations, preserves matrix size, and achieves sharper signal scaling than prior lossy cloning methods.It tightly achieves the scaling needed for sharper hardness results for ROSD and, indirectly, SPCAD over problems admitting sum-tests.Source: §7.1 · p. 49
• Reflection cloning can create information-theoretically detectable entries outside {−1, 0, 1}, limiting the hardness results to composite rather than canonical simple-versus-simple testing formulations.Such entries arise from collisions when reflected indices are both in the support; avoiding them would strengthen results for SSBMD, SSWD, ROSD, and SPCAD.Source: §7.1 · p. 49

7.2 Sparse Spiked Wigner Matrix

• Reflection cloning reduces planted clique to rank-1 submatrix, while the sparse spiked Wigner reduction preserves planted symmetry through diagonal planting, averaging, and added randomness.The latter incurs an arbitrarily small polynomial loss in spike size and also serves as a subroutine for the SSBMD reduction.Source: §7.1 · p. 52, §7.2 · p. 54

7.1 Reflecting Cloning and Rank-1 Submatrix

• Under the planted clique conjecture, randomized polynomial-time tests for ROSD have asymptotic Type I+II error at least 1 in the stated parameter regime.The paper identifies this as the computational boundary for ROSD in that regime.Source: §7.1 · p. 53

7.2 Sparse Spiked Wigner Matrix

• Theorem 7.5 gives planted-clique-based computational barriers for SROSD and SSWD, with parameter settings shifted by the reduction’s polynomial loss.The lower bound matches Theorem 7.3’s barrier, but the needed parameter settings differ.Source: §7.2 · p. 56
• The supplied 7.2 passages report a planted-clique-based error lower bound of at least 1 and say it yields computational boundaries for SROSD and Sparse Spiked Wigner, but omit the parameter regime.The fragments specify that the planted clique conjecture is assumed at density p = 1/2.Source: §7.2 · p. 56

7.3 Subgraph Stochastic Block Model

• Reflection cloning from planted clique to SROSD yields tight hardness for the subgraph stochastic block model, capturing sharper detection hardness than planted dense subgraph and the lack of a sum test.The reduction is formalized in Lemma 7.6, and the resulting lower bound is applied in Theorem 7.7.Source: §7.3 · pp. 56, 59
• In the stated parameter regime, randomized polynomial-time tests for the subgraph stochastic block model have asymptotic Type I+II error at least 1 under the planted clique conjecture.The theorem considers q = Θ(1), ρ = ˜Θ(n^-α), and k = ˜Θ(n^β), subject to its stated restrictions on α and β.Source: §7.3 · p. 59

8 Random Rotations and Sparse PCA

• Random-Rotation preserves Gaussian noise and maps a rank-1 signal to columns sampled independently from a Gaussian with covariance I_m + θvv⊤.The construction relies on random orthogonal rotation; Diaconis–Freedman’s theorem supports the approximation used in the sparse PCA reductions.Source: §8 · pp. 60–61
• SPCA-Low-Sparsity maps planted clique through biclustering to canonical simple-vs.-simple sparse PCA, while SPCA-High-Sparsity uses rank-1 submatrix and random rotation.The section describes the sparse PCA reductions as relatively simple, with much of the lower-bound work residing in reductions to biclustering and rank-1 submatrix.Source: §8 · pp. 60–63
• For k ≳ √n, the reductions give tight planted-clique hardness for SPCAD; sparse PCA lower bounds are not tight when k ≪ √n.The biased sparse PCA lower bounds are tight only at θ = ˜Θ(1).Source: §8 · pp. 61, 63
• The section’s lower-bound scope is regime-dependent: sparse PCA bounds are not tight for k ≪ √n, and biased sparse PCA bounds are tight only at θ = ˜Θ(1).The stated tight SPCAD result applies when k ≳ √n.Source: §8 · pp. 61, 63
• Under the planted dense subgraph recovery conjecture, exact support recovery in UBSPCAR is hard when θ ≪ 1.The same reduction gives partial- or weak-recovery hardness only if the corresponding planted-dense-subgraph conjecture is strengthened to those recovery tasks.Source: §8 · pp. 64–65

9.1 Biclustering, Planted Dense Subgraph and Independent Set

• For PDSD, the information-theoretic lower bound recovers the PIS/PDSD barrier when p = cq or p = 0, and a separate genie argument establishes weak-recovery impossibility for PISR.The cited PDSR recovery bounds do not cover PISR because p = 0 violates their condition on log p/(1−q).Source: §9.1 · pp. 66–67
• For BCR and PDSR, cited theorems characterize weak and exact recovery limits, including conditions under which recovery is possible and necessary conditions for it.The section also notes that the recovery lower bounds for BCR and PDSR are derived in.Source: §9.1 · pp. 66–67
• An inefficient algorithm for BCD and a similar one for PDSD attain the information-theoretic detection bounds; the PDSD result covers p = cq and yields the PIS algorithm by setting p = 0.The BCD procedure thresholds both the maximum k×k submatrix sum and the total input sum.Source: §9.1 · pp. 67–68
• Polynomial-time thresholding gives detection guarantees for BCD and PDSD, while recovery algorithms cover BCR, PDSR, and PISR and match the computational lower bounds.For PISR, the recovery algorithm applies a result to the complement graph.Source: §9.1 · p. 69

9.2 Rank-1 Submatrix, Sparse Spiked Wigner and Subgraph SBM

• The SROSD information-theoretic lower bound also holds for ROSD and SSWD, and data processing extends it to SSBMD when q = Θ(1).The SSBMD transfer thresholds matrix entries and then randomizes edges to obtain the target edge density.Source: §9.2 · pp. 70–71
• At µ ≥ c√(k log n), ROS-Search recovers both supports with probability at least 1−4n^-1, matching the information-theoretic limit while searching adaptively over sparsities and validating on an independent data copy.The theorem uses c1 = 1/2 and ρ = µ/k.Source: §9.2 · pp. 71, 74
• A simple test solves SSBMD, ROSD, and SSWD asymptotically down to their information-theoretic limits; for ROSD and SSWD it sets ρ = µ/k.The section states the SSBMD threshold in terms of ρ and the ROSD/SSWD thresholds in terms of µ.Source: §9.2 · p. 76
• For k ≲ √n, absolute-entry thresholding recovers supp(u) × supp(v) when µ ≥ 2k√(6 log n), while its µ ≳ k threshold matches planted-clique lower bounds up to polylogarithmic factors.Thresholding the maximum absolute entry also solves ROSD and SSWD when µ ≳ k.Source: §9.2 · p. 77
• ROS-Spectral-Projection achieves exact ROSR support recovery down to planted-clique lower bounds, and a spectral test solves ROSD with Type I+II error tending to zero under its signal condition.The section notes that the ROSD algorithm also solves SSWD because each SSWD instance is an ROSD instance.Source: §9.2 · p. 77
• For SSBMD with q = Θ(1) and k = Ω(√n), a spectral test based on the largest eigenvalue of A − qJ has Type I+II error tending to zero.The test outputs H1 when λ1(A − qJ) exceeds its stated threshold, and H0 otherwise.Source: §9.2 · p. 78

9.3 Sparse PCA and Biased Sparse PCA

• For SPCAD, gives an information-theoretic lower bound forcing optimal Type I+II error to 1 under its stated condition; closes the d = Θ(n) gap to thresholding’s upper bound.The earlier bound degrades when d ≪ k^2; when d = Θ(n), it had a gap from the best known thresholding algorithm before the improvement.Source: §9.3 · p. 78
• Information-theoretic detection lower bounds are established for both models, with different limits arising from the planted-vector ensembles used in sparse PCA and biased sparse PCA.For biased sparse PCA, the stronger lower bound uses a refined MGF argument; the section notes that the ensembles yield different information-theoretic limits.Source: §9.3 · p. 79
• Weak recovery for both sparse PCA and biased sparse PCA is impossible when θ ≲ k/n, matching the stated threshold.The result applies to estimators whose output and the planted support both have size k.Source: §9.3 · p. 80
• Searching over principal k × k minors for the largest eigenvalue gives information-theoretic algorithms for sparse PCA detection and estimation under the stated covariance-concentration condition.The section also presents empirical-covariance results for detection and ℓ2 estimation, specializing prior guarantees to Gaussian sparse PCA.Source: §9.3 · p. 81
• Semidefinite-programming algorithms provide polynomial-time detection and weak-recovery guarantees in the regime k ≲ √n.The section gives detection guarantees for sparse PCA and ℓ2-estimation guarantees that yield weak recovery for both models.Source: §9.3 · pp. 82–83
• For biased sparse PCA, a polynomial-time empirical-covariance sum test matches the stated upper bound and detects smaller signals than the spectral algorithm.For sparse PCA, a spectral test also gives polynomial-time detection under the theorem’s stated conditions.Source: §9.3 · pp. 83–84
• When d/n converges to a fixed c, thresholding the leading empirical-covariance eigenvector recovers the planted support exactly with probability tending to one.The section adapts a spectral algorithm to require only that the planted vector belongs to Vd,k.Source: §9.3 · p. 84

10 Detection-Recovery Reductions

• Detection lower bounds imply corresponding partial-recovery lower bounds through polynomial-time reductions that couple instances sharing a planted structure.A recovery output is restricted to its selected indices to produce a detection instance with a linear-size planted structure.Source: §10 · p. 84

Sparse PCA and Biased Sparse PCA.

• For sparse PCA and biased sparse PCA, the authors modify existing detection reductions to produce two copies rather than use a generic detection-recovery reduction.For sparse PCA, the resulting detection procedure uses one sample to select coordinates and a second to form an empirical covariance matrix; the stated signal threshold aligns with the information-theoretic lower bound.Source: §10 · p. 84, Sparse PCA and Biased Sparse PCA · p. 87

10 Detection-Recovery Reductions

• For biclustering, a recovery algorithm can be used as a black box in a polynomial-time detection algorithm, transferring detection lower bounds to partial recovery.The construction clones the input, then tests the sum over the row and column indices selected from the first copy.Source: §10 · pp. 85–86
• For sparse spiked Wigner and rank-1 submatrix problems, the reduction yields detection error tending to zero at signal levels aligned with the recovery information-theoretic lower bound.The passages also state that analogous reductions apply to SSW and therefore SSW’s recovery lower bounds follow.Source: §10 · p. 86
• For planted independent set, a recovery algorithm gives a reduction from PIS recovery to detection, while a similar two-copy construction yields a planted dense subgraph detection-recovery reduction.The PDS construction covers the parameter space p − q = O(q) by choosing w sufficiently small.Source: §10 · pp. 86–87

11 Future Directions

• Can a different planted-clique reduction yield lower bounds for the simple-hypothesis versions of SSWD, ROSD, SSBMD, and SPCAD?Reflection-Cloning collisions leave the paper’s formulations as composite-hypothesis tests.Source: §11 · p. 87
• The planted-clique lower bounds for SPCAD are not tight when k ≪ √n; the paper asks whether a reduction can make them tight in this regime.Source: §11 · p. 87
• The paper asks whether a polynomial-time recovery algorithm for SSBM can match the computational barrier for detection.Source: §11 · p. 87
• The paper asks whether the planted dense subgraph recovery conjecture can be derived from the planted clique conjecture.Source: §11 · p. 87

B Deferred Proofs from Section 3

• Conditioning on A changes the probability of any event B by at most P[Y ∈ A^c], with equality attained by choosing B = A.The proof uses this bound to establish the stated total variation result.Source: A Deferred Proofs from Section 3 · p. 97

B Deferred Proofs from Section 5

• rkP1 is computable in O(log n) time, while rkP2 is computable in O(n^K log n), hence polynomial time.The proofs invoke Lemma 5.1 for both procedures.Source: B Deferred Proofs from Section 5 · pp. 97–98
• The Gaussian procedure’s kernel can be computed and sampled in O(1) operations, and rkG is computable in polynomial time.The proof bounds its truncation parameter N by poly(n).Source: B Deferred Proofs from Section 5 · pp. 98–99
• For the Gaussian argument, a truncated region is chosen so that the probability outside it is bounded by Gaussian tail terms.The proof bounds the mass outside S using the tails at M − µ and M + µ.Source: B Deferred Proofs from Section 5 · p. 99
• For the Poisson argument, the proof obtains ∆ = O_n(n^-3) for sufficiently large n when q = Ω_n(1).It then applies Lemma 5.1 to conclude the lemma.Source: B Deferred Proofs from Section 5 · pp. 99–100

C Deferred Proofs from Section 6

• Randomized polynomial-time maps from PCD to PDSD have total variation tending to zero in the regimes treated by the proofs.The proofs invoke these maps with Lemma 3.1 to establish the stated reduction property.Source: C Deferred Proofs from Section 6 · pp. 100, 101, 104
• Theorem proofs exclude information-theoretically impossible parameter ranges before establishing their reductions.The stated exclusions include β < 2α in Theorem 6.4 and β < 2γ − α in Theorem 6.10.Source: C Deferred Proofs from Section 6 · pp. 101, 103
• Gaussian lifting followed by the stated transformations yields independent matrix entries, with shifted Gaussian means on planted off-diagonal positions and standard normal entries elsewhere.The planted positions are in S × S; diagonal entries remain standard normal.Source: C Deferred Proofs from Section 6 · p. 102
• The General-PDS reduction composes Gaussian lifting with a modified version of Poisson lifting.The proof checks parameter conditions before applying the cited lifting lemma.Source: C Deferred Proofs from Section 6 · p. 103

D Deferred Proofs from Section 7

• The ROS reduction constructs a prior supported on pairs of unit vectors with sparsity bounded by 2^ℓk.It conditions the prior on inequalities that hold with probability at least 1 − 8/k.Source: D Deferred Proofs from Section 7 · pp. 104–105
• The ROSD proof maps planted clique detection to ROSD under the null and to a prior over alternatives, with total variation tending to zero.The construction uses parameters based on ℓ_n, k_n, and N_n.Source: D Deferred Proofs from Section 7 · pp. 105–106
• The SROSD proof likewise reduces from planted clique detection to a detection problem under the null and a prior over alternatives.The proof assumes 2α ≤ β before setting its reduction parameters.Source: D Deferred Proofs from Section 7 · pp. 106–107
• The SSBMD theorem treats 2α ≤ β; when 2α > β, the model is stated to be information-theoretically impossible.The reduction also handles larger output graphs by padding and vertex permutation.Source: D Deferred Proofs from Section 7 · pp. 107–108
• For SSBMD, the proof reduces from planted clique detection and post-processes edges to obtain the target edge probabilities.For q below one half, it keeps each edge with probability 2q; for q above one half, it adds absent edges with probability 2q − 1.Source: D Deferred Proofs from Section 7 · p. 107

E Deferred Proofs from Section 8

• The proof of the distributional comparison conditions on the planted vectors and applies a random rotation with a sub-polynomially growing parameter.It then uses data processing and triangle inequalities.Source: E Deferred Proofs from Section 8 · p. 108
• A randomized polynomial-time map reduces planted clique detection to SPCAD under the null and a prior over alternatives, with total variation tending to zero.The proof assumes α ∈ (0, 1) and β > 1 − α.Source: E Deferred Proofs from Section 8 · p. 109
• For UBSPCAD, the proof gives a randomized polynomial-time reduction from planted clique detection with total variation tending to zero between the constructed alternative prior and target.The theorem assumes α ∈ (0, 1) after excluding α ≥ 1 as information-theoretically impossible.Source: E Deferred Proofs from Section 8 · p. 109
• The proof derives the USPCAD lower bound by randomly signing the rows of the resulting UBSPCAD instance.The UBSPCAD reduction maps planted clique detection to a detection problem under the null and a prior over alternatives, with total variation tending to zero.Source: E Deferred Proofs from Section 8 · p. 109

F Deferred Proofs from Section 9

• A vertex-membership proof reduces the task to testing two Bernoulli-product distributions, then uses the resulting testing error to obtain a contradiction.The proof provides the test with the graph, a sampled vertex, and the planted set with two vertices removed.Source: F Deferred Proofs from Section 9 · p. 110
• For PDS, tests based on total edge count or the densest k-vertex subgraph have vanishing Type I+II error under one of the stated conditions.The proof uses concentration bounds and reverses the test inequalities when p < q.Source: F Deferred Proofs from Section 9 · p. 111
• The support-recovery proof shows that its final two steps recover supp(r) and supp(c).The argument establishes coordinate separation before those steps.Source: F Deferred Proofs from Section 9 · p. 112
• A spectral algorithm for SSBMD has Type I+II error o(1) as n → ∞.The proof bounds the leading eigenvalue under the null and compares it with a planted-vector quadratic form under the alternative.Source: F Deferred Proofs from Section 9 · p. 113
• A chi-square comparison bounds the distance between the covariance-model alternative mixture and the null by a quantity tending to zero.The proof derives the bound from the overlap of two uniformly sampled k-subsets.Source: F Deferred Proofs from Section 9 · pp. 113–114
• The recovery argument establishes an algorithm achieving weak recovery with expected overlap k − o(k) as n → ∞.The conclusion follows after bounding coordinates inside and outside the planted support.Source: F Deferred Proofs from Section 9 · pp. 110, 116

Lemma 10.1

• Under the assumption on P and Q, the distributions used in Step 2 of PDS-Cloning are nonnegative and normalized.The proof checks nonnegativity after noting normalization.Source: G Deferred Proofs from Section 10 · p. 116
• The mixture identity gives x_ij ∼ Bern(Q)^⊗2 for edge probability q and x_ij ∼ Bern(P)^⊗2 for edge probability p.Consequently, the null and planted graph distributions map to the corresponding product distributions.Source: G Deferred Proofs from Section 10 · p. 116

Lemma 10.2

• For Lemma 10.2, joint Gaussianity and a zero-covariance relation imply independence, yielding independent M^k_ij entries for k = 1, 2.The proof also invokes independence of the entries of M and G.Source: G Deferred Proofs from Section 10 · p. 116