Reducibility and Statistical-Computational Gaps from Secret Leakage
summary
Introduces secret leakage planted clique, a generalization where clique locations follow a distribution rho and is conjectured hard whenever two independent samples have rapidly decaying overlap, recovering the usual k < sqrt(n) barrier; develops bernoulli rotations plus rejection kernels to change Bernoulli entries into Gaussians with only polylog attenuation and small total‑variation error; uses incidence geometry over finite fields to build column vectors A_i that produce the intended sparse vs outlier means; reduces k‑partite hypergraph planted clique to robust sparse mean estimation and explains the observed k versus k^2 computational gap.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 1:38The Problem
- 3:58Motivation
- 6:46Average case reduction
- 11:10Web of reductions
- 12:15What is Secret Leakage
- 14:31Average Case Reductions
- 21:55Bernoulli Rotations
- 24:54Problem Description
- 26:47Reduction
- 28:18Other Reductions
- 29:01Conclusions
- 30:32Lower Bounds
- 31:30Satisfaction Threshold
- 32:14Reductions
- 34:45General Reductions
- 39:58Conclusion
related talks
01h 07mA Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
42mUsing the Planted Clique Conjecture for Cryptography: Public-Key Encryption from...
13mPseudorandom Self-Reductions for NP-Complete Problems
49mRecent Advances in Counting Sparse Graphs
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
43mInformation-Theoretic Bounds and Phase Transitions in Community Detection and High-Dimensional Clust
01h 00mDifferential Privacy And The Complexity Of Simple Queries