37 citations · 101 across the 43 of their papers we have counts for
3 papers · 2 filters
Hypercontractive inequalities via SOS, and the Frankl--Rödl graph
Manuel Kauers, Ryan O'Donnell, Li-Yang Tan +1
Our main result is a formulation and proof of the reverse hypercontractive inequality in the sum-of-squares (SOS) proof system. As a consequence we show that for any constant $0 <…
New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, Li-Yang Tan +1
We show that given a 3-colorable graph, it is NP-hard to find a 3-coloring with $(16/17 + \eps)$ of the edges bichromatic. In a related result, we show that given a satisfiable ins…
On the Distribution of the Fourier Spectrum of Halfspaces
Ilias Diakonikolas, Ragesh Jaiswal, Rocco A. Servedio +2
Bourgain showed that any noise stable Boolean function can be well-approximated by a junta. In this note we give an exponential sharpening of the parameters of Bourgain's resul…