A Polynomial Time Algorithm for Lossy Population Recovery
summary
Proves a polynomial time algorithm for lossy population recovery for any fixed mu>0, showing recovery even when only ~1% of bits survive. Turns the problem into a badly conditioned linear system and constructs a robust local inverse via a convex program whose dual is ruled out by an uncertainty principle for polynomials. Analysis combines spectral methods with complex analysis, notably the Hadamard three-circle theorem, and yields a corollary: polytime learning of DNFs in the restriction access model.
AI-written summary · about
chapters (16)
- 0:00Intro
- 0:53Can you reconstruct a description of the population from these fragments?
- 3:15The Model (Dvir, Rao, Wigderson, Yehudayoff)
- 4:08Another Model (Wigderson, Yehudayoff)
- 4:42Theorem [Dvir et al ITCS 2012]: There is a polynomial time algorithm for any p ≥ 0.36 (lossy)
- 5:59An Application
- 8:33Restriction Access (Dvir et al)
- 10:31What is this talk about?
- 12:13The Setup
- 16:27Robust Local Inverse (Dvir et al)
- 21:02We can write an LP for finding a RLI
- 24:36An Uncertainty Principle?
- 26:08Relaxation #1
- 29:18Relaxation #2
- 30:04Hadamard Three Circle Theorem
- 31:32Outline
related talks
01h 11mPedagogical Talk: Failure of Low-Degree Polynomials
39mLocal Algorithms for Community Detection
09mConvex Programs, Computational Phase Transitions, and Robust Algorithms
11mUnderstanding Statistical-to-Computational Gaps via Low-Degree Polynomials
40mThe Trimmed Lasso: Sparse Recovery Guarantees And Practical Optimization
01h 11mStatistical Physics and Computation in High Dimension
43mLearning from Dynamics
01h 06mAnalytic Methods for Supervised Learning III