78 citations · 335 across the 44 of their papers we have counts for
15 papers · 1 filter
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan +1
We give a pseudorandom generator that fools degree- polynomial threshold functions over -dimensional Gaussian space with seed length . All previ…
Fooling Polytopes
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
We give a pseudorandom generator that fools -facet polytopes over with seed length . The previous best seed length had superlinear…
Sum of squares lower bounds for refuting any CSP
Pravesh K. Kothari, Ryuhei Mori, Ryan O'Donnell +1
Let be a nontrivial -ary predicate. Consider a random instance of the constraint satisfaction problem on variables with cons…
Optimal mean-based algorithms for trace reconstruction
Anindya De, Ryan O'Donnell, Rocco Servedio
In the (deletion-channel) trace reconstruction problem, there is an unknown -bit source string . An algorithm is given access to independent traces of , where a trace is f…
Quantum automata cannot detect biased coins, even in the limit
Guy Kindler, Ryan O`Donnell
Aaronson and Drucker (2011) asked whether there exists a quantum finite automaton that can distinguish fair coin tosses from biased ones by spending significantly more time in acce…
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…
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…
Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs
Ryan O'Donnell, John Wright, Chenggang Wu +1
Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic -…
A composition theorem for parity kill number
Ryan O'Donnell, Xiaorui Sun, Li-Yang Tan +2
In this work, we study the parity complexity measures and . is the \emph{parity kill…
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…
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 <…
Approximability and proof complexity
Ryan O'Donnell, Yuan Zhou
This work is concerned with the proof-complexity of certifying that optimization problems do \emph{not} have good solutions. Specifically we consider bounded-degree "Sum of Squares…
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…
A new point of NP-hardness for 2-to-1 Label Cover
Per Austrin, Ryan O'Donnell, John Wright
We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
Every decision tree has an influential variable
Ryan O'Donnell, Michael Saks, Oded Schramm +1
We prove that for any decision tree calculating a boolean function , \[ \Var[f] \le \sum_{i=1}^n δ_i \Inf_i(f), \] where is the probability that the…