Rigorous Evidence for Information-Computation Trade-offs
2021-09-13..2021-09-17
-- online --
who it's for
complexity theorists, high-dimensional statistics researchers, machine learning researchers, optimization researchers, algorithm designers, statistical physicists, privacy researchers
topics
low-degree polynomial methods; sum-of-squares lower bounds; planted clique reductions; average-case hardness reductions; memory-sample tradeoffs; approximate message passing (AMP); overlap gap property for inference; stochastic gradient descent escape phases; spectral methods for robust estimation; generative priors for signal recovery; phase transitions in spiked models; differential privacy query complexity
| title | author | length |
|---|---|---|
| Smoothed CSP Refutation Is As Easy As Random, For Both Efficient Algorithms And Certificates | Pravesh K. Kothari | 58m |
Shows that starting from any worst-case clause hypergraph and flipping each literal with small constant probability (e.g. 0.01) yields the same density–time… | ||
| Sum Of Squares Lower Bounds Versus Low-Degree Polynomial Lower Bounds | Aaron Potechin | 29m |
Compares low-degree polynomials and Sum-of-Squares via pseudo-calibration and gives a concrete inequality: a low-degree polynomial with mean C on the planted… | ||
| Planted Geometric Matching Problems | Dmitriy (Tim) Kunisky | 31m |
Model: points Xi ~ N(0,I) get Gaussian displacements with variance sigma^2, then permuted; estimator is the maximum likelihood estimator solved as a linear… | ||
| Robust Parameter Estimation For Random Graphs | Jayadev Acharya | 24m |
Establishes nearly tight upper and lower bounds for estimating p in G(n,p) with an adversary corrupting a γ fraction of nodes: a two-step algorithm uses a… | ||
| New Techniques For Proving Fine-Grained Average-Case Hardness | Andrea Lincoln | 44m |
A framework shows that if a worst‑case problem P equals a good low‑degree polynomial on {0,1} inputs (degree ≲ log n / log log n) and that polynomial is… | ||
| Charting the Landscape of Memory/Data Tradeoffs in Continuous Optimization: ... | Gregory Valiant | 45m |
Constrained-memory algorithms either store a basis or pay huge sample costs: over F2, algorithms with <~d^2/4 bits of memory require exponentially many samples… | ||
| Computational Barriers to Estimation from Low-Degree Polynomials | Tselil Schramm | 29m |
Considers the spiked Gaussian matrix model with K = N^alpha nonzeros and SNR lambda = N^{beta-alpha}, and shows a concrete lower bound: against no… | ||
| The Overlap Gap Property For Inference: Power And Limitations | Ilias Zadik | 36m |
Claim: the overlap gap property (OGP) for inference predicts where efficient algorithms fail by testing monotonicity of a restricted optimization curve… | ||
| To Be (Hard) or Not Be:... | Florent Krzakala | 36m |
Defines the spiked matrix-tensor model (rank‑one vector, noisy matrix plus p=3 tensor), computes the Bayes-optimal MMSE from the limiting free energy and… | ||
| Are Generative Models The New Sparsity? | Bruno Loureiro | 29m |
Generative priors sampled from random-weight neural nets reduce the algorithmic–statistical gap seen with sparsity in toy high-dimensional inference: rigorous… | ||
| A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness | Guy Bresler | 01h 07m |
Shows concrete polynomial-time maps from planted‑clique variants to many statistical tasks, claiming simple linear transforms explain apparent computational… | ||
| The Initial Search Phase Of Stochastic Gradient Descent For High-Dimensional Inference Tasks | Reza Gheissari | 30m |
Classifies how much data and time online SGD needs to escape the small‑correlation saddle at the origin: define an information exponent K (first nonzero… | ||
| Local Convexity Of The Tap Free Energy And Amp Convergence For Z2-Synchronization | Song Mei | 32m |
For Z2 synchronization at constant signal strength the result is that the TAP free energy has a single, locally strongly convex minimizer near the Bayes… | ||
| Signal Recovery With Generative Priors | Paul Hand | 33m |
Random ReLU feedforward generators with Gaussian weights and expansive layers are modeled as the prior and shown to permit compressive phase retrieval from… | ||
| All-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix Estimation | Cynthia Rush | 38m |
Shows that rank‑1 sparse spiked matrix estimation exhibits sharp all‑or‑nothing phase transitions as sparsity rho→0 and SNR λ→∞: the information‑theoretic… | ||
| Phase Retrieval In High Dimensions: Statistical And Computational Phase Transitions | Antoine Maillard | 35m |
Conjectures give an explicit replica symmetric potential whose maximizer yields the asymptotic MMSE; the formula is proven for Gaussian sensing matrices (real… | ||
| Mismatched Monte Carlo Algorithms For The Planted Clique Problem | Maria Chiara Angelini | 31m |
Jerrum Monte Carlo on perfect cliques gets trapped at random clique sizes and empirically remains superpolynomial until k scales like n^0.91 rather than √n, so… | ||
| Putting Quantum Supremacy on a Rigorous Footing | Umesh Vazirani | 01h 08m |
Google builds a superconducting device with 52 qubits and ~depth 20 circuits (≈1,000 gates, each failing ~1/100) and reports a linear cross-entropy score… | ||
| Optimizing Noncommutative Polynomials: The SYK Model | Ryan O'Donnell | 59m |
Random SYK Hamiltonians (Gaussian coefficients normalized so E[sum A_S^2]=1) live as implicit 2^{N/2}-dimensional Majorana matrices and have OPT(H) = Θ(√N)… | ||
| The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials | Brice Huang | 33m |
Shows that low-degree polynomial algorithms (degree ~log N, a class that simulates FIX) provably fail for Random k‑SAT once clause density exceeds a constant… | ||
| Tight Algorithmic Thresholds for Spin Glass Hamiltonians | Mark Sellke | 26m |
Provides a tight characterization of the algorithmic threshold ALG for optimizing mean-field spin glass Hamiltonians (Ising and spherical, even-degree models… | ||
| Average-Case Hardness in Proof Complexity | Susanna F. de Rezende | 59m |
Survey claims average-case refutation of random instances is the right way to prove strong proof-size lower bounds, and it demonstrates concrete tools… | ||
| Extractor-Based Approach To Memory-Sample Tradeoffs | Sumegha Garg | 45m |
The paper proves concrete memory–sample lower bounds by modeling learners as branching programs and using an extractor-based matrix condition (every large… | ||
| Optimal Spectral Recovery Of A Planted Vector In A Subspace | Alexander S Wein | 27m |
Recovery targets a structured vector hidden in a random D-dimensional subspace by observing an N×D basis matrix whose rows are IID samples that are Gaussian… | ||
| Refutation and Spectrally Quiet Planting of Cuts and Colorings in Random Graphs | Jess Banks | 23m |
Constructs a spectrally quiet planted model by taking random d-regular graphs as the null and sampling random lifts of a small k-colorable base so that the… | ||
| Differential Privacy And The Complexity Of Simple Queries | Jonathan Ullman | 01h 00m |
Shows an explicit information–computation gap: answering k arbitrary bounded mean queries privately needs about √k samples with any polynomial-time algorithm… | ||
| The Estimation Error of General First Order Methods | Michael Celentano | 27m |
Claims a concrete lower bound: for fixed T and n,p →∞ any general first‑order method (matrix multiplies + coordinatewise nonlinearities) reduces any… | ||
| Non-Gaussian Component Analysis: Statistical Query Hardness and its Applications | Ilias Diakonikolas | 29m |
Proves an SQ hardness theorem for Non‑Gaussian Component Analysis: if a univariate A matches the first m moments with N(0,1) and has finite chi-square… | ||
| SQ Lower Bounds for Learning Halfspaces with Massart Noise | Daniel Kane | 31m |
Proves an SQ lower bound: no statistical-query algorithm with polynomially many queries and polynomial accuracy learns a linear threshold function under… | ||
| Towards Lower Bounds for Efficient Robust Estimation From Worst Case Assumptions | Jerry Li | 31m |
Shows that beating O(sqrt(epsilon)) under only moment or resilience assumptions is probably impossible by reductions from small‑set expansion variants… | ||
| Computational Barriers For Learning Some Generalized Linear Models | Surbhi Goel | 30m |
Shows two concrete hardness results for ReLU GLMs: a conditional lower bound from Densest-kappa-subgraph hardness proving no poly(d) · 2^{Ω(1/ε^2)} time… | ||
| nothing matches | ||