14 citations · 56 across the 7 of their papers we have counts for
Showing 2015Show all
3 papers · 1 filter
cs.IT2015★ 9 cited
Remarks on the Most Informative Function Conjecture at fixed mean
Guy Kindler, Ryan O'Donnell, David Witmer
In 2013, Courtade and Kumar posed the following problem: Let be uniformly random, and form by negating each bit…
cs.CC2015★ 8 cited
How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
Let be a -ary predicate over a finite alphabet. Consider a random CSP instance over variables with constraints. When the instance will be unsa…
cs.CC2015★ 8 cited
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…