A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
summary
Shows concrete polynomial-time maps from planted‑clique variants to many statistical tasks, claiming simple linear transforms explain apparent computational gaps. Uses Bernoulli rotations (Gaussianization + linear embedding), reflection cloning / Gaussian cloning to resample and expand signal, and combinatorial Hadamard constructions (finite‑field hyperplane incidences) to control outlier fractions. Builds reductions to biclustering, rank‑one submatrix, tensor PCA, robust sparse mean/regression and SBM, preserving total‑variation and algorithmic thresholds up to mild parameter losses.
AI-written summary · about
chapters (12)
- 0:00Start
- 5:06Notion of Reduction
- 8:37Restricted Classes of Algorithms
- 13:40Robust Sparse Linear Regression
- 20:06Secret Leakage
- 26:22Changing Bernoulli To Gaussian
- 29:04Gaussian Sample Splitting or Gaussian Cloning
- 34:21Reflection Cloning
- 44:27Non-Robot Sparse Main Estimation
- 55:24Stochastic Block Models
- 55:36Stochastic Block Model
- 56:58Average Edge Density
related talks
41mReducibility and Statistical-Computational Gaps from Secret Leakage
37mA Bluffer's Guide to Dimension Reduction
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
01h 12mPedagogical Talk: Frameworks for Information-Computation Tradeoffs
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
01h 03mSampling for Linear Algebra, Statistics, and Optimization I
34mDimensionally reducing data squeezing out the good stuff
36mOptimizing with Tensors