Arrow Research search

Author name cluster

Ryan O'Donnell

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

51 papers
1 author row

Possible papers

51

STOC Conference 2025 Conference Paper

Explicit Two-Sided Vertex Expanders beyond the Spectral Barrier

  • Jun-Ting Hsieh
  • Ting-Chun Lin
  • Sidhanth Mohanty
  • Ryan O'Donnell
  • Rachel Yun Zhang

We construct the first explicit two-sided vertex expanders that bypass the spectral barrier. Previously, the strongest known explicit vertex expanders were given by d -regular Ramanujan graphs, whose spectral properties imply that every small subset of vertices S has at least 0.5 d | S | distinct neighbors. However, it is possible to construct Ramanujan graphs containing a small set S with no more than 0.5 d | S | neighbors. In fact, no explicit construction was known to break the 0.5 d -barrier. In this work, we give an explicit construction of an infinite family of d -regular graphs (for large enough d ) where every small set expands by a factor of ≈ 0.6 d . More generally, for large enough d 1 , d 2 , we give an infinite family of ( d 1 , d 2 )-biregular graphs where small sets on the left expand by a factor of ≈ 0.6 d 1 , and small sets on the right expand by a factor of ≈ 0.6 d 2 . In fact, our construction satisfies an even stronger property: small sets on the left and right have unique-neighbor expansion 0.6 d 1 and 0.6 d 2 respectively. Our construction follows the tripartite line product framework of Hsieh et. al., and instantiates it using the face-vertex incidence of the 4-dimensional Ramanujan clique complex as its base component. As a key part of our analysis, we derive new bounds on the triangle density of small sets in the Ramanujan clique complex.

Details

FOCS Conference 2023 Conference Paper

Explicit orthogonal and unitary designs

  • Ryan O'Donnell
  • Rocco A. Servedio
  • Pedro Paredes 0002

We give a strongly explicit construction of ϵ approximate k-designs for the orthogonal group O(N) and the unitary group U(N), for $N=2^{n}$. Our designs are of cardinality $\operatorname{poly}(N^{k}/\epsilon)$ (equivalently, they have seed length $O(nk+\log(1/\epsilon)))$; up to the polynomial, this matches the number of design elements used by the construction consisting of completely random matrices.

Details

SODA Conference 2023 Conference Paper

Mean estimation when you have the source code; or, quantum Monte Carlo methods

  • Robin Kothari
  • Ryan O'Donnell

Suppose y is a real random variable, and one is given access to “the code” that generates it (for example, a randomized or quantum circuit whose output is y ). We give a quantum procedure that runs the code O ( n ) times and returns an estimate for μ = E [ y ] that with high probability satisfies, where σ = stddev[ y ]. This dependence on n is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse. Our method improves upon previous works, which either made additional assumptions about y, and/or assumed the algorithm knew an a priori bound on σ, and/or used additional logarithmic factors beyond O(n). The central subroutine for our result is essentially Grover's algorithm but with complex phases. * The full version of the paper can be accessed at https: //arxiv. org/abs/2208. 07544

Details

FOCS Conference 2023 Conference Paper

Query-optimal estimation of unitary channels in diamond distance

  • Jeongwan Haah
  • Robin Kothari
  • Ryan O'Donnell
  • Ewin Tang

We consider process tomography for unitary quantum channels. Given access to an unknown unitary channel acting on a d-dimensional qudit, we aim to output a classical description of a unitary that is $\varepsilon$-close to the unknown unitary in diamond norm. We design an algorithm achieving error $\varepsilon$ using $O\left(\mathrm{~d}^{2} / \varepsilon\right)$ applications of the unknown channel and only one qudit. This improves over prior results, which use $O\left(\mathrm{~d}^{3} / \varepsilon^{2}\right)$ [via standard process tomography] or $O\left(\mathrm{~d}^{2. 5} / \varepsilon\right)$ [Yang, Renner, and Chiribella, PRL 2020] applications. To show this result, we introduce a simple technique to “bootstrap” an algorithm that can produce constant-error estimates to one that can produce $\varepsilon$-error estimates with the Heisenberg scaling. Finally, we prove a complementary lower bound showing that estimation requires $\Omega\left(\mathrm{d}^{2} / \varepsilon\right)$ applications, even with access to the inverse or controlled versions of the unknown unitary. This shows that our algorithm has both optimal query complexity and optimal space complexity.

Details

STOC Conference 2022 Conference Paper

Optimizing strongly interacting fermionic Hamiltonians

  • Matthew B. Hastings
  • Ryan O'Donnell

The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree- q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q =4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.

Details

FOCS Conference 2020 Conference Paper

Explicit near-fully X-Ramanujan graphs

  • Ryan O'Donnell
  • Xinyu Wu

Let p(Y1, .. ., Yd, Z1, .. ., Ze) be a self-adjoint noncommutative polynomial, with coefficients from C r×r, in the indeterminates Y1, .. ., Yd (considered to be self-adjoint), the indeterminates Z1, .. ., Ze, and their adjoints Z1*, .. ., Ze*. Suppose Y1, .. ., Yd are replaced by independent random n x n matching matrices, and Z1, .. ., Ze are replaced by independent random n x n permutation matrices. Assuming for simplicity that p's coefficients are 0-1 matrices, the result can be thought of as a kind of random rn-vertex graph G. As n goes to infinity, there will be a natural limiting infinite graph X that covers any finite outcome for G. A recent landmark result of Bordenave and Collins shows that for any, with high probability the spectrum of a random G will be eps-close in Hausdorff distance to the spectrum of X (once the suitably defined “trivial” eigenvalues are excluded). We say that G is “eps-near fully X-Ramanujan”. Our work has two contributions: First we study and clarify the class of infinite graphs X that can arise in this way. Second, we derandomize the Bordenave-Collins result: for any X, we provide explicit, arbitrarily large graphs G that are covered by X and that have (nontrivial) spectrum at Hausdorff distance at most eps from that of X. This significantly generalizes the recent work of Mohanty et al. , which provided explicit near-Ramanujan graphs for every degree d (meaning d-regular graphs with all nontrivial eigenvalues bounded in magnitude by 2sqrt(d-1) + eps). As an application of our main technical theorem, we are also able to determine the “eigenvalue relaxation value” for a wide class of average-case degree-2 constraint satisfaction problems.

Details

STOC Conference 2020 Conference Paper

Explicit near-Ramanujan graphs of every degree

  • Sidhanth Mohanty
  • Ryan O'Donnell
  • Pedro Paredes 0002

For every constant d ≥ 3 and є > 0, we give a deterministic poly( n )-time algorithm that outputs a d -regular graph on Θ( n ) vertices that is є-near-Ramanujan; i.e., its eigenvalues are bounded in magnitude by 2√ d −1 + є (excluding the single trivial eigenvalue of d ).

Details

STOC Conference 2019 Conference Paper

Quantum state certification

  • Costin Badescu
  • Ryan O'Donnell
  • John Wright 0004

We consider the problem of quantum state certification , where one is given n copies of an unknown d -dimensional quantum mixed state ρ, and one wants to test whether ρ is equal to some known mixed state σ or else is є-far from σ. The goal is to use notably fewer copies than the Ω( d 2 ) needed for full tomography on ρ (i.e., density estimation). We give two robust state certification algorithms: one with respect to fidelity using n = O ( d /є) copies, and one with respect to trace distance using n = O ( d /є 2 ) copies. The latter algorithm also applies when σ is unknown as well. These copy complexities are optimal up to constant factors.

Details

STOC Conference 2017 Conference Paper

Sum of squares lower bounds for refuting any CSP

  • Pravesh K. Kothari
  • Ryuhei Mori
  • Ryan O'Donnell
  • David Witmer

Let P :{0,1} k → {0,1} be a nontrivial k -ary predicate. Consider a random instance of the constraint satisfaction problem ( P ) on n variables with Δ n constraints, each being P applied to k randomly chosen literals. Provided the constraint density satisfies Δ ≫ 1, such an instance is unsatisfiable with high probability. The refutation problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate P supports a t - wise uniform probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree d = Θ( n /Δ 2/( t -1) logΔ) (which runs in time n O ( d ) ) cannot refute a random instance of ( P ). In particular, the polynomial-time SOS algorithm requires Ω( n ( t +1)/2 ) constraints to refute random instances of CSP( P ) when P supports a t -wise uniform distribution on its satisfying assignments. Together with recent work of Lee, Raghavendra, Steurer (2015), our result also implies that any polynomial-size semidefinite programming relaxation for refutation requires at least Ω( n ( t +1)/2 ) constraints. More generally, we consider the δ-refutation problem, in which the goal is to certify that at most a (1 - δ)-fraction of constraints can be simultaneously satisfied. We show that if P is δ-close to supporting a t -wise uniform distribution on satisfying assignments, then the degree-Θ( n /Δ 2/( t - 1) logΔ) SOS algorithm cannot (δ+ o (1))-refute a random instance of CSP( P ). This is the first result to show a distinction between the degree SOS needs to solve the refutation problem and the degree it needs to solve the harder δ-refutation problem. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate P , they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen, O'Donnell, Witmer (2015) and Raghavendra, Rao, Schramm (2016), this full three-way tradeoff is tight , up to lower-order factors.

Details

STOC Conference 2016 Conference Paper

Efficient quantum tomography

  • Ryan O'Donnell
  • John Wright 0004

In the quantum state tomography problem, one wishes to estimate an unknown d -dimensional mixed quantum state ρ, given few copies. We show that O ( d /ε) copies suffice to obtain an estimate ρ that satisfies ||ρ − ρ|| F 2 ≤ ε (with high probability). An immediate consequence is that O ((ρ) · d /ε 2 ) ≤ O ( d 2 /ε 2 ) copies suffice to obtain an ε-accurate estimate in the standard trace distance. This improves on the best known prior result of O ( d 3 /ε 2 ) copies for full tomography, and even on the best known prior result of O ( d 2 log( d /ε)/ε 2 ) copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension. Next, we generalize these results to show that one can perform efficient principal component analysis on ρ. Our main result is that O ( k d /ε 2 ) copies suffice to output a rank- k approximation ρ whose trace-distance error is at most ε more than that of the best rank- k approximator to ρ. This subsumes our above trace distance tomography result and generalizes it to the case when ρ is not guaranteed to be of low rank. A key part of the proof is the analogous generalization of our spectrum-learning results: we show that the largest k eigenvalues of ρ can be estimated to trace-distance error ε using O ( k 2 /ε 2 ) copies. In turn, this result relies on a new coupling theorem concerning the Robinson–Schensted–Knuth algorithm that should be of independent combinatorial interest.

Details

FOCS Conference 2015 Conference Paper

How to Refute a Random CSP

  • Sarah R. Allen
  • Ryan O'Donnell
  • David Witmer

Let P be a k-ary predicate over a finite alphabet. Consider a random CSP(P) instance I over n variables with m constraints. When m ≫ n the instance will be unsatisfiable with high probability and we want to find a certificate of unsatisfiability. When P is the 3-ary OR predicate, this is the well-studied problem of refuting random 3-SAT formulas and an efficient algorithm is known only when m ≫ n 3/2. Understanding the density required for refutation of other predicates is important in cryptography, proof complexity, and learning theory. Previously, it was known that for a k-ary predicate, having m ≫≫n [k/2] constraints suffices for refutation. We give a criterion for predicates that often yields efficient refutation algorithms at much lower densities. Specifically, if P fails to support a t-wise uniform distribution, then there is an efficient algorithm that refutes random CSP(P) instances whp when m ≫ n t/2. Indeed, our algorithm will “somewhat strongly” refute the instance I, certifying Opt(I) ≤ 1 - Ωk(1). If t = k then we get the strongest possible refutation, certifying Opt(I) ≤ E[P] + o(1). This last result is new even for random k-SAT. Prior work on SDP hierarchies has given some evidence that efficient refutation of random CSP(P) may be impossible when m ≫ n t/2; thus there is an indication that our algorithm's dependence on m is optimal for every P, at least in the context of SDP hierarchies. As an application of our result, we falsify assumptions used to show hardness-of-learning in recent work of Daniely, Linial, and Shalev-Shwartz.

Details

STOC Conference 2015 Conference Paper

Quantum Spectrum Testing

  • Ryan O'Donnell
  • John Wright 0004

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given n copies of a mixed state ρ∈ C d x d and the goal is to distinguish (with high probability) whether ρ's spectrum satisfies some property P or whether it is at least ε-far in l 1 -distance from satisfying P. This problem was promoted under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Unlike property testing probability distributions---where one generally hopes for algorithms with sample complexity that is sublinear in the domain size---here the hope is for algorithms with subquadratic copy complexity in the dimension d. This is because the (frequently rediscovered) "empirical Young diagram (EYD) algorithm" [ARS88,KW01,HM02,CM06] can estimate the spectrum of any mixed state up to ε-accuracy using only O(d 2 /ε 2 ) copies. In this work, we show that given a mixed state ρ ∈ C d x d : Θ(d/ε 2 ) copies are necessary and sufficient to test whether ρ is the maximally mixed state, i.e., has spectrum (1/d, ..., 1/d). This can be viewed as the quantum analogue of a result of Paninski [Pan08]. Θ(r 2 /ε) copies are necessary and sufficient to test with one-sided error whether ρ has rank r, i.e., has at most r nonzero eigenvalues. For two-sided error, a lower bound of Ω(r/ε) copies holds. Θ(r 2 ) copies are necessary and sufficient to distinguish whether ρ is maximally mixed on an r-dimensional or an (r+1)-dimensional subspace. More generally, for r vs. r+Δ (with 1 ≤ Δ ≤ r), Θ(r 2 /Δ) copies are necessary and sufficient. The EYD algorithm requires Ω(d 2 /ε 2 ) copies to estimate the spectrum of ρ up to ε-accuracy, nearly matching the known upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

Details

SODA Conference 2014 Conference Paper

Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs

  • Ryan O'Donnell
  • John Wright 0004
  • Chenggang Wu 0003
  • Yuan Zhou 0007

Building on work of Cai, Fürer, and Immerman [18], we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic n -vertex graphs G and H such that any sum-of-squares (SOS) proof of nonisomorphism requires degree Ω( n ). In other words, we show an Ω( n )-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs G and H which are not even (1 – 10 −14 )-isomorphic. (Here we say that two n -vertex, m -edge graphs G and H are α -isomorphic if there is a bijection between their vertices which preserves at least αm edges.) Our second result is that under the R3XOR Hypothesis [23] (and also any of a class of hypotheses which generalize the R3XOR Hypothesis), the robust Graph Isomorphism is hard. I. e. for every ∊ > 0, there is no efficient algorithm which can distinguish graph pairs which are (1 — ∊)-isomorphic from pairs which are not even (1 – ∊ 0 )-isomorphic for some universal constant ∊ 0. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

Details

SODA Conference 2014 Conference Paper

Testing Surface Area

  • Pravesh K. Kothari
  • Amir Nayyeri
  • Ryan O'Donnell
  • Chenggang Wu 0003

We consider the problem of estimating the surface area of an unknown n -dimensional set F given membership oracle access. In contrast to previous work, we do not assume that F is convex, and in fact make no assumptions at all about F. By necessity this means that we work in the property testing model; we seek an algorithm which, given parameters A and ∊, satisfies: if surf( F ) ≤ A then the algorithm accepts (whp); if F is not ∊-close to some set G with surf ( G ) ≤ κA, then the algorithm rejects (whp). We call κ ≥ 1 the “approximation factor” of the testing algorithm. The n = 1 case (in which “surf( F ) = 2 m ” means F is a disjoint union of m intervals) was introduced by Kearns and Ron [KR98], who solved the problem with κ = 1/∊ and O (1/∊) oracle queries. Later, Balcan et al. [BBBY12] solved it with with κ = 1 and O (1/∊ 4 ) queries. We give the first result for higher dimensions n. Perhaps surprisingly, our algorithm completely evades the “curse of dimensionality”: for any n and any κ > we give a test that uses O (1/∊) queries. For small n we have improved bounds. For n = 1 we can achieve κ = 1 with O (1/∊ 3. 5 ) queries (slightly improving [BBBY12]), or any κ > 1 with O (1/∊) queries (improving [KR98]). For n = 2, 3 we obtain κ ≈ 1. 08, 1. 125 respectively, with O (1/∊) queries. Getting an arbitrary κ > 1 for n > 1 remains an open problem.

Details

SODA Conference 2013 Conference Paper

Approximability and proof complexity

  • Ryan O'Donnell
  • Yuan Zhou 0007

This work is concerned with the proof-complexity of certifying that optimization problems do not have good solutions. Specifically we consider bounded-degree “Sum of Squares” (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof is automatizable using semidefinite programming (SDP), meaning that any n -variable degree- d proof can be found in time n O ( d ). Furthermore, the SDP is dual to the well-known Lasserre SDP hierarchy, meaning that the “ d /2-round Lasserre value” of an optimization problem is equal to the best bound provable using a degree- d SOS proof. These ideas were exploited in a recent paper by Barak et al. (STOC 2012) which shows that the known “hard instances” for the Unique-Games problem are in fact optimally solved by a constant level of the Lasserre SDP hierarchy. We continue the study of the power of SOS proofs in the context of difficult optimization problems. In particular, we show that the Balanced-Separator integrality gap instances proposed by Devanur et al. can have their optimal value certified by a degree-4 SOS proof. The key ingredient is an SOS proof of the KKL Theorem. We also investigate the extent to which the Khot–Vishnoi Max-Cut integrality gap instances can have their optimum value certified by an SOS proof. We show they can be certified to within a factor. 952 (>. 878) using a constant-degree proof. These investigations also raise an interesting mathematical question: is there a constant-degree SOS proof of the Central Limit Theorem?

Details

FOCS Conference 2013 Conference Paper

Learning Sums of Independent Integer Random Variables

  • Constantinos Daskalakis
  • Ilias Diakonikolas
  • Ryan O'Donnell
  • Rocco A. Servedio
  • Li-Yang Tan

Let bS = bX_1 + ·s + bX_n be a sum of n independent integer random variables bX_i, where each bX_i is supported on 0, 1, ·, k-1 but otherwise may have an arbitrary distribution (in particular the bX_i's need not be identically distributed). How many samples are required to learn the distribution bS to high accuracy? In this paper we show that the answer is completely independent of n, and moreover we give a computationally efficient algorithm which achieves this low sample complexity. More precisely, our algorithm learns any such bS to ε-accuracy (with respect to the total variation distance between distributions) using poly(k, 1/ε) samples, independent of n. Its running time is poly(k, 1/ε) in the standard word RAM model. Thus we give a broad generalization of the main result of DDS12stoc which gave a similar learning result for the special case k=2 (when the distribution bS is a Poisson Binomial Distribution). Prior to this work, no nontrivial results were known for learning these distributions even in the case k=3. A key difficulty is that, in contrast to the case of k = 2, sums of independent 0, 1, 2-valued random variables may behave very differently from (discretized) normal distributions, and in fact may be rather complicated - they are not log-concave, they can be θ(n)-modal, there is no relationship between Kolmogorov distance and total variation distance for the class, etc. Nevertheless, the heart of our learning result is a new limit theorem which characterizes what the sum of an arbitrary number of arbitrary independent 0, 1, ·, k-1-valued random variables may look like. Previous limit theorems in this setting made strong assumptions on the "shift invariance" of the random variables bX_i in order to force a discretized normal limit. We believe that our new limit theorem, as the first result for truly arbitrary sums of independent 0, 1, ·, k-1-valued random variables, is of independent interest.

Details

STOC Conference 2012 Conference Paper

A new point of NP-hardness for unique games

  • Ryan O'Donnell
  • John Wright 0004

We show that distinguishing 1/2-satisfiable Unique-Games instances from (3/8 + ε)-satisfiable instances is NP-hard (for all ε > 0). A consequence is that we match or improve the best known c vs. s NP-hardness result for Unique-Games for all values of c (except for c very close to 0). For these c, ours is the first hardness result showing that it helps to take the alphabet size larger than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the ETH.

Details

FOCS Conference 2009 Conference Paper

KKL, Kruskal-Katona, and Monotone Nets

  • Ryan O'Donnell
  • Karl Wimmer

We generalize the Kahn-Kalai-Linial (KKL) Theorem to random walks on Cayley and Schreier graphs, making progress on an open problem of Hoory, Linial, and Wigderson. In our generalization, the underlying group need not be abelian so long as the generating set is a union of conjugacy classes. An example corollary is that for every f: ( k [n] ) ¿ {0, 1} with E[f] and k/n bounded away from 0 and 1, there is a pair 1 ¿ i ij (f) ¿ ¿(log n/n). Here l ij (f) denotes the "influence" on / of swapping the ith and jth coordinates. Using this corollary we obtain a "robust" version of the Kruskal-Katona Theorem: Given a constant-density subset A of a middle slice of the Hamming n-cube, the density of ¿A is greater by at least ¿(log n/n), unless A is noticeably correlated with a single coordinate. As an application of these results, we show that the set of functions {0, 1, x 1, .. ., x ¿, Maj} is a (1/2-¿)-net for the set of all n-bit monotone boolean functions, where ¿ = ¿(log n//¿(n)). This distance is optimal for polynomial-size nets and gives an optimal weak-learning algorithm for monotone functions under the uniform distribution, solving a problem of Blum, Burch and Langford.

Details

STOC Conference 2008 Conference Paper

An optimal sdp algorithm for max-cut, and equally optimal long code tests

  • Ryan O'Donnell
  • Yi Wu 0002

Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 ≤ c ≤ 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [1/2,1] -> [1/2,1] by GapSDP(c) = inf{s : (c, s) is an SDP gap}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] by determining the entire SDP gap curve; we show GapSDP(c) = S(c) for a certain explicit (but complicated to state) function S. In particular, our lower bound GapSDP(c) - S(c) is proved via a polynomial-time - RPR 2 ' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR 2 confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR 2 algorithm can be guaranteed to find cuts of value larger than S(c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S(c) SDP gap, our RPR 2 algorithm actually finds the optimal cut.) - Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P ≠ NP and the Unique Games Conjecture.

Details

FOCS Conference 2008 Conference Paper

Learning Geometric Concepts via Gaussian Surface Area

  • Adam R. Klivans
  • Ryan O'Donnell
  • Rocco A. Servedio

We study the learnability of sets in Ropf n under the Gaussian distribution, taking Gaussian surface area as the "complexity measure" of the sets being learned. Let C S denote the class of all (measurable) sets with surface area at most S. We first show that the class C S is learnable to any constant accuracy in time n O(S 2 ), even in the arbitrary noise ("agnostic'') model. Complementing this, we also show that any learning algorithm for C S information-theoretically requires 2 Omega(S 2 ) examples for learning to constant accuracy. These results together show that Gaussian surface area essentially characterizes the computational complexity of learning under the Gaussian distribution. Our approach yields several new learning results, including the following (all bounds are for learning to any constant accuracy): The class of all convex sets can be agnostically learned in time 2 O ~ (radicn) (and we prove a 2 Omega(radicn) lower bound for noise-free learning). This is the first subexponential time algorithm for learning general convex sets even in the noise-free (PAC) model. Intersections of k halfspaces can be agnostically learned in time n O(log k) (cf. Vempala's n O(k) time algorithm for learning in the noise-free model). Cones (with apex centered at the origin), and spheres witharbitrary radius and center, can be agnostically learned in time poly(n).

Details

STOC Conference 2008 Conference Paper

Some topics in analysis of boolean functions

  • Ryan O'Donnell

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 bounds to higher-degree polynomials; and, hardness for approximation algorithms.

Details

FOCS Conference 2008 Conference Paper

Spherical Cubes and Rounding in High Dimensions

  • Guy Kindler
  • Ryan O'Donnell
  • Anup Rao 0001
  • Avi Wigderson

What is the least surface area of a shape that tiles Ropf d under translations by Zopf d? Any such shape must have volume 1 and hence surface area at least that of the volume-1 ball, namely Omega(radicd). Our main result is a construction with surface area O(radicd), matching the lower bound up to a constant factor of 2radic2pi/eap3. The best previous tile known was only slightly better than the cube, having surface area on the order of d. We generalize this to give a construction that tiles Ropf d by translations of any full rank discrete lattice Lambda with surface area 2piparV -1 par fb, where V is the matrix of basis vectors of Lambda, and par. par fb denotes the Frobenius norm. We show that our bounds are optimal within constant factors for rectangular lattices. Our proof is via a random tessellation process, following recent ideas of Raz in the discrete setting. Our construction gives an almost optimal noise-resistant rounding scheme to round points in Ropf d to rectangular lattice points.

Details

FOCS Conference 2006 Conference Paper

SDP gaps and UGC-hardness for MAXCUTGAIN

  • Subhash Khot
  • Ryan O'Donnell

Given a graph with maximum cut of (fractional) size c, the Goemans-Williamson semidefinite programming (SDP) algorithm by M. Goemans and D. Williamson (1995) is guaranteed to find a cut of size. 878 middot c. However this guarantee becomes trivial when c is near frac12, since a random cut has expected size frac12. Recently, M. Charikar and K. Worth (2004) (analyzing an algorithm of U. Feige and G. Langberg (2001)) showed that given a graph with maximum cut frac12 + epsiv, one can find a cut of size frac12 + Omega(epsiv/ log(1/epsiv)). The main contribution of our paper is twofold: 1. We give a natural frac12 + epsiv vs. frac12 + O(epsiv/ log(1/epsiv)) SDP gap for MAXCUT in Gaussian space. This shows that the SDP-rounding algorithm of Charikar-Worth is essentially best possible. Further, the "s-linear rounding functions" used in the works of M. Charikar and K. Worth (2004) and U. Freige and M. Langberg (2001) arise as optimizers in our analysis, somewhat confirming a suggestion of U. Freige and M. Langberg (2001). 2. We show how this SDP gap can be translated into a long code test with the same parameters. This implies that beating the Charikar-Worth guarantee with any efficient algorithm is NP-hard, assuming the unique games conjecture (UGC) by S. Khot (2002). We view this result as essentially settling the approximability of MAXCUT, assuming UGC. Building on (1) we show how "randomness reduction" on related SDP gaps for the QUADRATICPROGRAMMING programming problem lets us make the Omega(log(1/epsiv)) gap as large as Omega(log n) for n-vertex graphs. In addition to optimally answering an open question of N. Alen et al. (2006), this technique may prove useful for other SDP gap problems. Finally, illustrating the generality of our technique in (2), we also show how to translate Reeds's SDP gap by J. Reeds (1993) for the Grothendieck Inequality into a UGC-hardness result for computing the par middot par infin rarr 1 norm of a matrix

Details

FOCS Conference 2005 Conference Paper

Every decision tree has an in. uential variable

  • Ryan O'Donnell
  • Michael E. Saks
  • Oded Schramm
  • Rocco A. Servedio

We prove that for any decision tree calculating a Boolean function f: {-1, 1}/sup n/ /spl rarr/ {-1, 1}, Var[f] /spl les/ /spl Sigma/ /sub i=1/ /sup n/ /spl delta//sup i/Inf/sub i/(f), i = 1 where /spl delta//sup i/ is the probability that the ith input variable is read and Inf/sub i/(f) is the influence of the ith variable on f. The variance, influence and probability are taken with respect to an arbitrary product measure on {-1, 1}/sup n/n. It follows that the minimum depth of a decision tree calculating a given balanced function is at least the reciprocal of the largest influence of any input variable. Likewise, any balanced Boolean function with a decision tree of depth d has a variable with influence at least 1/d. The only previous nontrivial lower bound known was /spl Omega/(d2/sup -d/). Our inequality has many generalizations, allowing us to prove influence lower bounds for randomized decision trees, decision trees on arbitrary product probability spaces, and decision trees with nonBoolean outputs. As an application of our results we give a very easy proof that the randomized query complexity of nontrivial monotone graph properties is at least/spl Omega/(v/sup 4/3//p/sup 1/3/), where v is the number of vertices and p /spl les/ 1/2 is the critical threshold probability. This supersedes the milestone /spl Omega/(v/sup 4/3//p/sup 1/3/) bound of Hajnal (1991) and is sometimes superior to the best known lower bounds of Chakrabarti-Khot (2001) and Friedgut-Kahn-Wigderson (2002).

Details

FOCS Conference 2005 Conference Paper

Learning mixtures of product distributions over discrete domains

  • Jon Feldman
  • Ryan O'Donnell
  • Rocco A. Servedio

We consider the problem of learning mixtures of product distributions over discrete domains in the distribution learning framework introduced by Kearns et al. (1994). We give a poly(n//spl epsi/) time algorithm for learning a mixture of k arbitrary product distributions over the n-dimensional Boolean cube {0, 1}/sup n/ to accuracy /spl epsi/, for any constant k. Previous poly(n)-time algorithms could only achieve this for k = 2 product distributions; our result answers an open question stated independently in M. Cryan (1999) and Y. Freund and Y. Mansour (1999). We further give evidence that no polynomial time algorithm can succeed when k is superconstant, by reduction from a notorious open problem in PAC learning. Finally, we generalize our poly(n//spl epsi/) time algorithm to learn any mixture of k = O(1) product distributions over {0, 1, .. ., b }/sup n/, for any b = O(1).

Details

FOCS Conference 2005 Conference Paper

Noise stability of functions with low in. uences invariance and optimality

  • Elchanan Mossel
  • Ryan O'Donnell
  • Krzysztof Oleszkiewicz

In this paper, we study functions with low influences on product probability spaces. The analysis of Boolean functions f {-1, 1}/sup n/ /spl rarr/ {-1, 1} with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics. We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known non-linear invariance principles. It has the advantage that its proof is simple and that the error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly "smoothed"; this extension is essential for our applications to "noise stability "-type problems. In particular; as applications of the invariance principle we prove two conjectures: the "Majority Is Stablest" conjecture [29] from theoretical computer science, which was the original motivation for this work, and the "It Ain't Over Till It's Over" conjecture [27] from social choice theory. The "Majority Is Stablest" conjecture and its generalizations proven here, in conjunction with the "Unique Games Conjecture" and its variants, imply a number of (optimal) inapproximability results for graph problems.

Details

FOCS Conference 2004 Conference Paper

Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?

  • Subhash Khot
  • Guy Kindler
  • Elchanan Mossel
  • Ryan O'Donnell

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate to within a factor of /spl alpha//sub cw/+ /spl epsi/, for all /spl epsi/ > 0, where /spl alpha//sub cw/ denotes the approximation ratio achieved by the Goemans-Williamson algorithm (1995). /spl alpha//sub cw/ /spl ap/. 878567. This result is conditional, relying on two conjectures: a) the unique games conjecture of Khot; and, b) a very believable conjecture we call the majority is stablest conjecture. These results indicate that the geometric nature of the Goemans-Williamson algorithm might be intrinsic to the MAX-CUT problem. The same two conjectures also imply that it is NP-hard to (/spl beta/ + /spl epsi/)-approximate MAX-2SAT, where /spl beta/ /spl ap/. 943943 is the minimum of (2 + (2//spl pi/) /spl theta/)/(3 - cos(/spl theta/)) on (/spl pi//2, /spl pi/). Motivated by our proof techniques, we show that if the MAX-2CSP and MAX-2SAT problems are slightly restricted - in a way that seems to retain all their hardness -then they have (/spl alpha//sub GW/-/spl epsi/)- and (/spl beta/ - /spl epsi/)-approximation algorithms, respectively. Though we are unable to prove the majority is stablest conjecture, we give some partial results and indicate possible directions of attack. Our partial results are enough to imply that MAX-CUT is hard to (3/4 + 1/(2/spl pi/) + /spl epsi/)-approximate (/spl ap/. 909155), assuming only the unique games conjecture. We also discuss MAX-2CSP problems over non-Boolean domains and state some related results and conjectures. We show, for example, that the unique games conjecture implies that it is hard to approximate MAX-2LIN(q) to within any constant factor.

Details

FOCS Conference 2003 Conference Paper

Learning DNF from Random Walks

  • Nader H. Bshouty
  • Elchanan Mossel
  • Ryan O'Donnell
  • Rocco A. Servedio

We consider a model of learning Boolean functions from examples generated by a uniform random walk on {0, 1}/sup n/. We give a polynomial time algorithm for learning decision trees and DNF formulas in this model. This is the first efficient algorithm for learning these classes in a natural passive learning model where the learner has no influence over the choice of examples used for learning.

Details

STOC Conference 2003 Conference Paper

Learning juntas

  • Elchanan Mossel
  • Ryan O'Donnell
  • Rocco A. Servedio

We consider a fundamental problem in computational learning theory: learning an arbitrary Boolean function which depends on an unknown set of k out of n Boolean variables. We give an algorithm for learning such functions from uniform random examples which runs in time roughly (n k ) ω/(ω + 1) , where ω < 2.376 is the matrix multiplication exponent. We thus obtain the first polynomial factor improvement on the naive n k time bound which can be achieved via exhaustive search. Our algorithm and analysis exploit new structural properties of Boolean functions.

Details

FOCS Conference 2002 Conference Paper

Learning Intersections and Thresholds of Halfspaces

  • Adam R. Klivans
  • Ryan O'Donnell
  • Rocco A. Servedio

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any function of a polylog number of polynomial-weight halfspaces under any distribution. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low degree polynomial threshold functions.

Details