Approximating the Permanent of a Random Matrix with Vanishing Mean

on YouTube ↗46m

" summary

Shows that exact permanent remains #P-hard on average for Gaussian matrices with vanishing mean, but approximation becomes quasi-polynomial time once the mean is as large as about 1/polylog n. Proof uses zeros of random polynomials plus analytic interpolation: Taylor-expand log of a univariate permanent polynomial, bound needed derivative order by counting roots (expected number inside radius R is Θ(R^2) via Jensen), then continue along random root-free curves and compute derivatives (cost ~n^M) to reconstruct the value.

AI-written summary · about

" chapters (12)

1. 0:00Start
2. 1:00Outline
3. 2:49Main question
4. 4:48Consider the classical process
5. 8:48Boson Sampling: Aaronson Arkhipov '10 Quantum analog of the mentioned process
6. 12:52Quantum advantage via Boson Sampling Sampling within total variation distance from a Boson computer is hard assuming plausible conjectures
7. 14:55The hardness landscape for the permanent
8. 25:53Primary challenges
9. 34:10Alternative method
10. 35:36Open questions
11. 38:46Connection with anti-concentration bounds
12. 39:42Observation