Computational Aliasing: A Nyquist Theory of Statistical-to-Computational Gaps

This paper develops a unified framework for statistical-to-computational gaps in planted inference problems, grounded in an analogy between computational intractability and Nyquist aliasing in signal processing. A statistical-to-computational gap occurs when a detection or recovery problem is information-theoretically solvable but apparently intractable for efficient algorithms — a phenomenon observed across planted clique, sparse PCA, tensor PCA, community detection, and many other canonical problems in theoretical computer science and statistics. The central object introduced is the spectral Nyquist rate ρ(𝒞, P₀, G) — a quantity computable from the null model alone — which governs the sharp phase transition between computational recovery and computational aliasing. Above ρ, an algorithm in class 𝒞 achieves non-trivial detection; below ρ, no such algorithm succeeds. Crucially, ρ does not depend on the planted signal, enabling prediction of the computational threshold for any planted structure against a given noise model without solving the detection problem (the ρ-from-P₀ principle). Main results include: The Computational Nyquist Theorem, establishing ρ as the sharp detection threshold for planted inference, with the spectral Nyquist rate characterized by the Stieltjes transform of the null model's limiting spectral distribution via the Baik–Ben Arous–Péché transition. The Barrier Unification Theorem, showing that low-degree polynomial, sum-of-squares, statistical query, and overlap gap property barriers all lower-bound ρ through formally distinct but equivalent mechanisms — providing a structural explanation for the longstanding empirical agreement across these independent frameworks. The Universal OGP–Stieltjes Correspondence, proving that the overlap gap property holds if and only if the signal eigenvalue falls below ρ for all matrix-representable planted problems satisfying mild regularity conditions, with the forbidden overlap window boundary computable from the Stieltjes transform alone. The Low-Degree Equivalence Bridge, establishing formal equivalence between the Stieltjes-derived ρ and the low-degree likelihood ratio threshold for all matrix-representable problems. The Dichotomy Characterization Theorem, giving necessary and sufficient conditions for the AAC conservation identity to hold as equality, separating strategic from entropic obfuscation. The Replica–Nyquist Correspondence, proving that ρ equals the de Almeida–Thouless stability threshold for replica-symmetric null models, formally connecting random matrix theory, TCS barriers, and statistical physics. The Structure Group Decomposition Theorem and Computational Friction Irrelevance Theorem (for spectral and low-degree polynomial classes). Quantitative verification against sixteen problem families (planted clique, planted dense subgraph, spiked Wigner, spiked Wishart, tensor PCA, sparse PCA, planted biclique, sparse tensor PCA, planted coloring, robust mean estimation, Gaussian mixture detection, low-rank matrix completion, random planted k-SAT, asymmetric stochastic block models, planted submatrix, inhomogeneous planted dense subgraph), with novel testable predictions confirmed by Monte Carlo where available. The framework is formally embedded within the Adversarial Aggregation Channel (AAC) program via the Diagonal Intersection Principle, establishing that every planted inference problem with a statistical-to-computational gap is an object in the impossibility category Imp with ρ as its adversarial rank. This paper is a companion to the AAC unification paper and the social choice Nyquist paper in that program.