Extended Formulations and Information Complexity

on YouTube ↗29m

" summary

Defines non-negative rank of the slack matrix and uses an entropy sampling reduction to show any factorization with R terms would let one sample a size-3^n distribution with ≤log R + n bits, so R must be exponential. Applies this to the correlation polytope, embedding unique disjointness as a submatrix, and concludes exponential lower bounds on extension complexity (and stronger approximate lower bounds up to n^{1−ε}).

AI-written summary · about

" chapters (10)

1. 0:00Introduction
2. 0:16Example
3. 2:50Extended Formulations
4. 5:01TSP Polytope
5. 7:25History
6. 11:00Factorization Theorem
7. 11:39Slack Matrix
8. 13:19NonNegative Rank
9. 15:34General Framework
10. 27:34Summary

" related talks

• 01h 00mMatrix Rank – Extensions, Applications and Open ProblemsAvi Widgerson · Geometric Complexity Theory 2014
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 56mEntropy, Capacity, and CountingNisheeth Vishnoi · Deterministic Counting, Probability, and Zeros of Partition Functions (Simons Institute workshop, 2019)
• 01h 37mMatrix RigiditySatya Lokam · Algorithms and Complexity in Algebraic Geometry Boot Camp 2014
• 50mRandom Combinatorial MatricesAmin Coja-Oghlan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 58mDichotomy Theorems for Counting Problems IXi Chen · Counting Complexity and Phase Transitions Boot Camp
• 01h 09mInformation Theory in Computational Complexity IVJaikumar Radhakrishnan · Information Theory Boot Camp 2015
• 27mA Lower Bound for k-DNF Resolution on Random CNF Formulas via ExpansionAnastasia Sofronova · Proof Complexity and Meta-Mathematics 2023