Approximating the Permanent of Positive Semidefinite Matrices
summary
Proves a deterministic algorithm that approximates the permanent of any positive semidefinite matrix to a simply exponential factor (≈ e^{γ+1}^n), using a concrete sandwich: an optimally chosen diagonal upper bound and a rank‑one lower bound whose permanents are easy to compute. Main tools are complex Gaussians to show nonnegativity, the Schur power matrix for monotonicity, and a convex program (and its dual correlation matrix) plus a random projection argument controlling a GM/AM ratio ≈ e^{−γ}. Analysis is tight.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 0:42Hard to Compute
- 1:42Approximations
- 4:22Proof
- 9:45Full Proof
- 12:03Approximating
- 15:33Sketch
- 23:30Norms
related talks
55mNon-commutative Computation
01h 31mTutorial 1: The GCT Chasm I
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
01h 01mTrue Complexity of Multilinear Systems
32mReed-Muller and Other Subcodes of the Sierpinski Matrix
17mSatisfiability Algorithms Based on Concentrated Shrinkage
01h 28mTutorial 4: GCT and Matrix Multiplication
20mSuperDP: Differential Privacy Refutation via Supermartingales