Hypercontractive inequalities via SOS, with an application to Vertex-Cover

Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, Yuan Zhou

Type: Preprint

Publication Date: 2012-12-21

Citations: 3

Locations

arXiv (Cornell University) - View

Similar Works

Action	Title	Year	Authors
+	Hypercontractive inequalities via SOS, and the Frankl--Rödl graph	2012	Manuel Kauers Ryan O’Donnell Li-Yang Tan Yuan Zhou
+	A stress-free sum-of-squares lower bound for coloring	2021	Pravesh K. Kothari Peter Manohar
+ PDF Chat	Hypercontractive inequalities via SOS, and the Frankl–Rödl graph	2013	Manuel Kauers Ryan O’Donnell Li-Yang Tan Yuan Zhou
+	A Stress-Free Sum-of-Squares Lower Bound for Coloring	2021	Pravesh K. Kothari Peter Manohar
+	Lifting sum-of-squares lower bounds: degree-2 to degree-4	2020	Sidhanth Mohanty Prasad Raghavendra Jeff Xu
+ PDF Chat	Hypercontractive inequalities via SOS, and the Frankl--Rödl graph	2016	Li-Yang Tan Yuan Zhou Ryan O’Donnell Manuel Kauers
+	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover	2020	Nikhil Bansal Jatin Batra Majid Farhadi Prasad Tetali
+	Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover	2020	Nikhil Bansal Jatin Batra Majid Farhadi Prasad Tetali
+	Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy	2011	Siavosh Benabbas Siu On Chan Konstantinos Georgiou Avner Magen
+ PDF Chat	Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs	2024	Pravesh K. Kothari Aaron Potechin Jeff Xu
+ PDF Chat	Simple Graph Density Inequalities with No Sum of Squares Proofs	2020	Grigoriy Blekherman Annie Raymond Mohit Singh Rekha R. Thomas
+	Simple Graph Density Inequalities with no Sum of Squares Proofs	2018	Grigoriy Blekherman Annie Raymond Mohit Singh Rekha R. Thomas
+	Simple Graph Density Inequalities with no Sum of Squares Proofs	2018	Grigoriy Blekherman Annie Raymond Mohit Singh Rekha R. Thomas
+	Lift & Project Systems Performing on the Partial-Vertex-Cover Polytope	2014	Κωνσταντίνος Γεωργίου Andy Jiang Edward Lee Astrid A. Olave Ian Seong Twesh Upadhyaya
+	Combinatorial Optimization via the Sum of Squares Hierarchy	2022	Goutham Rajendran
+	High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts	2017	Monaldo Mastrolilli
+ PDF Chat	High Degree Sum of Squares Proofs, Bienstock--Zuckerberg Hierarchy, and Chvátal--Gomory Cuts	2020	Monaldo Mastrolilli
+ PDF Chat	Sum-of-squares hierarchy lower bounds for symmetric formulations	2019	Adam Kurpisz Samuli Leppänen Monaldo Mastrolilli
+	Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lov&#x0E9;sz-Schrijver Hierarchy	2007	Stefan Dziembowski Krzysztof Pietrzak
+	Sum-of-squares hierarchy lower bounds for symmetric formulations	2014	Adam Kurpisz Samuli Leppänen Monaldo Mastrolilli

Works That Cite This (3)

Action	Title	Year	Authors
+	Hardness of robust graph isomorphism, lasserre gaps, and asymmetry of random graphs	2014	Ryan O’Donnell John C. Wright Chenggang Wu Yuan Zhou
+ PDF Chat	Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs	2013	Ryan O’Donnell John C. Wright Chenggang Wu Yuan Zhou
+	Analysis of Boolean Functions	2014	Ryan O’Donnell

Works Cited by This (0)

Action	Title	Year	Authors