Report

Hypercontractive inequalities via SOS, and the Frankl-Rödl graph Manuel Kauers (Johannes Kepler Universität) Ryan O’Donnell (Carnegie Mellon University) Li-Yang Tan (Columbia University) Yuan Zhou (Carnegie Mellon University) The hypercontractive inequalities • Real functions on Boolean cube: f : {-1,1}n ® R • Noise operator: Tr f (x) = E [ f (y)] y~ r x y ~ r x means each yi is r -correlated with xi Projection to deg-k • The hypercontractive inequality: Tr f q £ f p when 1 £ p £ q £ ¥, 0 £ r £ £k p-1 q-1 P f £ (q -1) f 2 , "q ³ 2 Corollary. q £k k/2 P f £3 f 2 24 hypercontractive ineq. 4 k/2 The hypercontractive inequalities • The reverse hypercontractive inequaltiy: Tr f q ³ f p when -¥ £ q £ p £1, 0 £ r £ Not norms Corollary [MORSS12]. when f, g : {-1,1} ® R , 0 £ q £1, 0 £ r £1- q n we have ³0 E [ f (x)g(y)] ³ E éë f (x)q ùû E éëg(y)q ùû x~ r y x y 1/q 1/q 1-p 1-q The hypercontractive inequalities • The hypercontractive inequality: p-1 Tr f q £ f p when 1 £ p £ q £ ¥, 0 £ r £ q-1 Applications: KKL theorem, Invariance Principle • The reverse hypercontractive inequaltiy: Tr f q ³ f p when -¥ £ q £ p £1, 0 £ r £ Applications: hardness of approximation, quantitative social choice 1-p 1-q The sum-of-squares (SOS) proof system • Closely related to the Lasserre hierarchy [BBHKSZ12, OZ13, DMN13] – Used to prove that Lasserre succeeds on specific instances • In degree-d SOS proof system To show a polynomial p(x1, x2,… , xn ) ³ 0, 2 write p(x1, x2 ,… , xn ) = åri (x1, x2,… , xn ) i where each ri has degree at most d Previous works • Deg-4 SOS proof of 24 hypercon. ineq. [BBHKSZ12] – Level-2 Lasserre succeeds on known UniqueGames instances • Constant-deg SOS proof of KKL theorem [OZ13] – Level-O(1) Lasserre succeeds on the BalancedSeparator instances by [DKSV06] • Constant-deg SOS proof of “2/π-theorem” [OZ13] and Majority-Is-Stablest theorem [DMN13] – Level-O(1) Lasserre succeeds on MaxCut instances by [KV05, KS09, RS09] Results in this work • Deg-q SOS proof of the hypercon. ineq. when p=2, q=2s n f , f ,… , f :{-1,1} ® R, r £ 1/ (q -1) for 1 2 s s és 2ù 2ù é E P (T f (x)) £ P E f (x) we have r i i ë û ú xê i=1 i=1 x ë û • Deg-4k SOS proof of reverse hypercon. ineq. when q= 21k for f, g :{-1,1}n ® R³0 , 0 £ r £1- 2k1 2k 2k 1/(2k ) 1/(2k ) ù E ég(y) ù we have E [ f (x)g(y)] ³ E éë f (x) û ë û x~ r y ff^(2k) gg^(2k) x y 2k 2k 2k 2k ù é E ë f (x) g(y) û ³ E [ f (x)] E [ g(y)] x~ r y x y Application of the reverse hypercon. ineq. to the Lasserre SDP • Frankl-Rödl graphs FRg (V, E) = FRg ({-1,1} ,{(x, y) : D(x, y) = (1- g )n}) n n n • 3-Coloring n – c (FR1/4 [FR87,GMPT11] ) = w (1) – SDPs by Kleinberg-Goemans fails to certify n c (FR1/4 )>3 [KMS98, KG98, Cha02] – Arora and Ge [AG11]: level-poly(n) Lasserre SDP n certifies c (FR1/4 )³4 – Our SOS proof: level-2 Lasserre SDP certifies n c (FR1/4 ) = w (1) Application of the reverse hypercon. ineq. to the Lasserre SDP • Frankl-Rödl graphs FRg (V, E) = FRg ({-1,1} ,{(x, y) : D(x, y) = (1- g )n}) n n n • VertexCover – Min-VC(FRgn ) >1- o(1) when g ³ .1 [FR87,GMPT11] log n n n level-6 – Level-ω(1) LS+SDP and SA+SDP fails to certify Min-VC(FR ) > 1 + W(1) g 2 [BCGM11] – The only known (2-o(1)) gap instances for SDP relaxations n – Our Min-VC(FR SOS proof: level-(1/γ) 1 g >>certifies ) >1- o(1)Lasserre SDP g logn Proof sketches • SOS proof of the normal hypercon. ineq. – Induction • SOS proof of the reverse hypercon. ineq. – Induction + computer-algebra-assisted induction • From reverse hypercon. ineq. to Frankl-Rödl graphs – SOS-ize the “density” variation of the Frankl-Rödl theorem due to Benabbas-Hatami-Magen [BHM12] SOS proof (sketch) of the reverse hypercon. ineq. • Statement: for f, g :{-1,1} ® R , 0 £ r £1- 2k1 exists SOS proof of n ³0 2k 2k 2k 2k ù é E ë f (x) g(y) û ³ E [ f (x)] E [ g(y)] x~ r y x y • Proof. Induction on n. – Base case (n = 1). For F0 , F1,G0 ,G1 ³ 0 – Key challenge, will prove later. • Statement: for f, g :{-1,1} ® R , 0 £ r £1- 2k1 exists SOS proof of n ³0 2k 2k 2k 2k ù é E ë f (x) g(y) û ³ E [ f (x)] E [ g(y)] x~ r y x y • Proof. Induction on n. – Base case (n = 1). For F0 , F1,G0 ,G1 ³ 0 – Induction step (n > 1). f0 (x1,… , xn-1) = f (x1,… , xn-1,-1) f1 (x1,… , xn-1) = f (x1,… , xn-1,1) Induction on (n-1) variables • Statement: for f, g :{-1,1} ® R , 0 £ r £1- 2k1 exists SOS proof of n ³0 2k 2k 2k 2k ù é E ë f (x) g(y) û ³ E [ f (x)] E [ g(y)] x~ r y x y • Proof. Induction on n. – Base case (n = 1). For F0 , F1,G0 ,G1 ³ 0 – Induction step (n > 1). f0 (x1,… , xn-1) = f (x1,… , xn-1, 0) f1 (x1,… , xn-1) = f (x1,… , xn-1,1) Induction by base case Proof of the base case • Assume w.l.o.g. F0 + F1 = G0 +G1 =1 • “Two-point ineq.” (where r* =1- 2k1 ): • Use the following substitutions: s = a + b, t = ab. Pk (a, b) where To show SOS proof of Pk (a, b) where ³0 By the Fundamental Theorem of Algebra, a univariate polynomial is SOS if it is nonnegative. Only need to prove Qk,0 ,Q k,i are nonnegative. To show SOS proof of Pk (a, b) where ³0 Proof of Qk,0 (t) ³ 0 : Case 1. (t < 0) Straightforward. Case 2. (t ³ 0) With the assistance of Zeilberger's alg. [Zei90, PWZ97], then its relatively easy to check Qk,0 (t) ³ 0 To show SOS proof of Pk (a, b) where ³0 Proof of Qk,i (t) ³ 0: By convexity, enough to prove ³0 By guessing the form of a polynomial recurrence and solving via computer, Finally prove the nonnegativity by induction. Summary of the proof • Induction on the number of variables • Base case: “two-point” inequality – Variable substitution – Prove the nonnegativity of a class of univariate polynomials • Via the assistance of computer-algebra algorithms, find out proper closed form or recursions • Prove directly or by induction Open questions • Is there constant-degree SOS proof for Min-VC(FRgn ) >1- o(1) when g ³ .1 logn n ? Recall that we showed a (1/γ)-degree proof 1 when g >> logn . Thanks!