Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ryan O'Donnell:

TR16-147 | 19th September 2016
Ryan O'Donnell, A. C. Cem Say

The weakness of CTC qubits and the power of approximate counting

Revisions: 1

We present two results in structural complexity theory concerned with the following interrelated
topics: computation with postselection/restarting, closed timelike curves (CTCs), and
approximate counting. The first result is a new characterization of the lesser known complexity
class BPP_path in terms of more familiar concepts. Precisely, BPP_path is the class of ... more >>>

TR16-142 | 11th September 2016
Jason Li, Ryan O'Donnell

Bounding laconic proof systems by solving CSPs in parallel

Revisions: 1

We show that the basic semidefinite programming relaxation value of any constraint satisfaction problem can be computed in NC; that is, in parallel polylogarithmic time and polynomial work. As a complexity-theoretic consequence we get that MIP1$[k,c,s] \subseteq $ PSPACE provided $s/c \leq (.62-o(1))k/2^k$, resolving a question of Austrin, HÃ¥stad, and ... more >>>

TR16-141 | 11th September 2016
Ryan O'Donnell

SOS is not obviously automatizable, even approximately

Revisions: 1

Suppose we want to minimize a polynomial $p(x) = p(x_1, \dots, x_n)$, subject to some polynomial constraints $q_1(x), \dots, q_m(x) \geq 0$, using the Sum-of-Squares (SOS) SDP hierarachy. Assume we are in the "explicitly bounded" ("Archimedean") case where the constraints include $x_i^2 \leq 1$ for all $1 \leq i \leq ... more >>>

TR14-091 | 22nd July 2014
Ryan O'Donnell, A. C. Cem Say

One time-travelling bit is as good as logarithmically many

Revisions: 1

We consider computation in the presence of closed timelike curves (CTCs), as proposed by Deutsch. We focus on the case in which the CTCs carry classical bits (as opposed to qubits). Previously, Aaronson and Watrous showed that computation with polynomially many CTC bits is equivalent in power to PSPACE. On ... more >>>

TR10-006 | 11th January 2010
YI WU, Ryan O'Donnell, David Zuckerman, Parikshit Gopalan

Fooling functions of halfspaces under product distributions

Revisions: 2

We construct pseudorandom generators that fool functions of halfspaces (threshold functions) under a very broad class of product distributions. This class includes not only familiar cases such as the uniform distribution on the discrete cube, the uniform distribution on the solid cube, and the multivariate Gaussian distribution, but also includes ... more >>>

TR09-130 | 1st December 2009
Ryan O'Donnell, YI WU, Yuan Zhou

Optimal lower bounds for locality sensitive hashing (except when $q$ is tiny)

We study lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that $\mathcal{H}$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y \in \{0,1\}^d$ with dist$(x,y) \leq r$ have probability at least $p$ ... more >>>

TR08-055 | 19th May 2008
Ryan O'Donnell

Some Topics in Analysis of Boolean Functions

This article accompanies a tutorial talk given at the 40th ACM STOC conference. In it, we give a brief introduction to Fourier analysis of boolean functions and then discuss some applications: Arrow?s Theorem and other ideas from the theory of Social Choice; the Bonami-Beckner Inequality as an extension of Chernoff/Hoeffding ... more >>>

TR07-128 | 10th November 2007
Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco Servedio

Testing Halfspaces

This paper addresses the problem of testing whether a Boolean-valued function f is a halfspace, i.e. a function of the form f(x)=sgn(w ⋅ x - θ). We consider halfspaces over the continuous domain R^n (endowed with the standard multivariate Gaussian distribution) as well as halfspaces over the Boolean cube {-1,1}^n ... more >>>

TR07-043 | 7th May 2007
Uriel Feige, Guy Kindler, Ryan O'Donnell

Understanding Parallel Repetition Requires Understanding Foams

Motivated by the study of Parallel Repetition and also by the Unique
Games Conjecture, we investigate the value of the ``Odd Cycle Games''
under parallel repetition. Using tools from discrete harmonic
analysis, we show that after $d$ rounds on the cycle of length $m$,
the value of the game is ... more >>>

TR05-101 | 20th September 2005
Guy Kindler, Ryan O'Donnell, Subhash Khot, Elchanan Mossel

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX-CUT to within a factor of $\GW + \eps$, for all $\eps > 0$; here $\GW \approx .878567$ denotes the approximation ratio achieved by the Goemans-Williamson algorithm~\cite{GW95}. This implies that if the Unique ... more >>>

ISSN 1433-8092 | Imprint