11 citations · 11 across the 2 of their papers we have counts for
3 papers · 1 filter
A composition theorem for the Fourier Entropy-Influence conjecture
Ryan O'Donnell, Li-Yang Tan
The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai [FK96] seeks to relate two fundamental measures of Boolean function complexity: it states that $H[f] \leq C Inf…
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…
Average sensitivity and noise sensitivity of polynomial threshold functions
Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio +1
We give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree- polynomial threshold functions (PTFs). These bounds hold both for PTFs ove…