Extended Formulations 4
summary
Shows how any bounded density F on {0,1}^n that tests indistinguishably against a family of functions D1 … Dm is approximated by a normalized exponential of a small weighted sum of those tests with multiplicative weights updates giving at most O((log ||F||_∞) · max_i ||Di||_∞^2 / η^2) terms so inner products match up to η. Extends to PSD matrix valued Q and yields a square of a low degree matrix polynomial approximation. Used to turn Sherali Adams and SOS gap instances into LP and SDP lower bounds for the correlation polytope via random restriction and factorization rescaling.
AI-written summary · about