BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Ryan O'Donnell contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We give a pseudorandom generator that fools degree-$d$ polynomial threshold functions over $n$-dimensional Gaussian space with seed length $\mathrm{poly}(d)\cdot \log n$. All previous generators had a seed length with at least a $2^d$ dependence on $d$. The key new ingredient is a Local Hyperconcentration Theorem, which shows that every degree-$d$ Gaussian polynomial is hyperconcentrated almost everywhere at scale $d^{-O(1)}$.
Let $Φ$ be an irreducible root system (other than $G_2$) of rank at least $2$, let $\mathbb{F}$ be a finite field with $p = \operatorname{char} \mathbb{F} > 3$, and let $\mathrm{G}(Φ,\mathbb{F})$ be the corresponding Chevalley group. We describe a strongly explicit high-dimensional expander (HDX) family of dimension $\mathrm{rank}(Φ)$, where $\mathrm{G}(Φ,\mathbb{F})$ acts simply transitively on the top-dimensional faces; these are $λ$-spectral HDXs with $λ\to 0$ as $p \to \infty$. This generalizes a construction of Kaufman and Oppenheim (STOC 2018), which corresponds to the case $Φ= A_d$. Our work gives three new families of spectral HDXs of any dimension $\ge 2$, and four exceptional constructions of dimension $4$, $6$, $7$, and $8$.
Suppose $\boldsymbol{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 $\boldsymbol{y}$). We give a quantum procedure that runs the code $O(n)$ times and returns an estimate $\widehat{\boldsymbolμ}$ for $μ= \mathrm{E}[\boldsymbol{y}]$ that with high probability satisfies $|\widehat{\boldsymbolμ} - μ| \leq σ/n$, where $σ= \mathrm{stddev}[\boldsymbol{y}]$. This dependence on $n$ is optimal for quantum algorithms. One may compare with classical algorithms, which can only achieve the quadratically worse $|\widehat{\boldsymbolμ} - μ| \leq σ/\sqrt{n}$. Our method improves upon previous works, which either made additional assumptions about $\boldsymbol{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.ally Grover's algorithm but with complex phases.
Let $p(Y_1, \dots, Y_d, Z_1, \dots, Z_e)$ be a self-adjoint noncommutative polynomial, with coefficients from $\mathbb{C}^{r \times r}$, in the indeterminates $Y_1, \dots, Y_d$ (considered to be self-adjoint), the indeterminates $Z_1, \dots, Z_e$, and their adjoints $Z_1^*, \dots, Z_e^*$. Suppose $Y_1, \dots, Y_d$ are replaced by independent random $n \times n$ matching matrices, and $Z_1, \dots, Z_e$ are replaced by independent random $n \times 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 \to \infty$, 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 $\varepsilon > 0$, with high probability the spectrum of a random $G$ will be $\varepsilon$-close in Hausdorff distance to the spectrum of $X$ (once the suitably defined "trivial" eigenvalues are excluded). We say that $G$ is "$\varepsilon$-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 $\varepsilon$ 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 $2\sqrt{d-1} + \varepsilon$). 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.
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 $ρ\in\mathbb{C}^{d\times d}$ and the goal is to distinguish whether $ρ$'s spectrum satisfies some property $\mathcal{P}$ or is at least $ε$-far in $\ell_1$-distance from satisfying $\mathcal{P}$. This problem was promoted in the survey of Montanaro and de Wolf 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. Here, the hope is for algorithms with subquadratic copy complexity in the dimension $d$. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to $ε$-accuracy using only $\widetilde{O}(d^2/ε^2)$ copies. In this work, we show that given a mixed state $ρ\in\mathbb{C}^{d\times d}$: (i) $Θ(d/ε^2)$ copies are necessary and sufficient to test whether $ρ$ is the maximally mixed state, i.e., has spectrum $(\frac1d, ..., \frac1d)$; (ii) $Θ(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; (iii) $\widetildeΘ(r^2/Δ)$ copies are necessary and sufficient to distinguish whether $ρ$ is maximally mixed on an $r$-dimensional or an $(r+Δ)$-dimensional subspace; and (iv) The EYD algorithm requires $Ω(d^2/ε^2)$ copies to estimate the spectrum of $ρ$ up to $ε$-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.
Let $X_1, \dots, X_n$ be joint $\{ \pm 1\}$-valued random variables. It is known that conditioning on a random subset of $O(1/ε^2)$ of them reduces their average pairwise covariance to below $ε$ (in expectation). We conjecture that $O(1/ε^2)$ can be improved to $O(1/ε)$. The motivation for the problem and our conjectured improvement comes from the theory of global correlation rounding for convex relaxation hierarchies. We suggest attempting the conjecture in the case that $X_1, \dots, X_n$ are the leaves of an information flow tree. We prove the conjecture in the case that the information flow tree is a caterpillar graph (similar to a two-state hidden Markov model).
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 $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 {\sc R3XOR} Hypothesis \cite{Fei02} (and also any of a class of hypotheses which generalize the {\sc R3XOR} Hypothesis), the \emph{robust} Graph Isomorphism problem 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.
We describe a web of connections between the following topics: the mathematical theory of voting and social choice; the computational complexity of the Maximum Cut problem; the Gaussian Isoperimetric Inequality and Borell's generalization thereof; the Hypercontractive Inequality of Bonami; and, the analysis of Boolean functions. A major theme is the technique of reducing inequalities about Gaussian functions to inequalities about Boolean functions f : {-1,1}^n -> {-1,1}, and then using induction on n to further reduce to inequalities about functions f : {-1,1} -> {-1,1}. We especially highlight De, Mossel, and Neeman's recent use of this technique to prove the Majority Is Stablest Theorem and Borell's Isoperimetric Inequality simultaneously.
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[f]$ holds for every Boolean function $f$, where $H[f]$ denotes the spectral entropy of $f$, $Inf[f]$ is its total influence, and $C > 0$ is a universal constant. Despite significant interest in the conjecture it has only been shown to hold for a few classes of Boolean functions. Our main result is a composition theorem for the FEI conjecture. We show that if $g_1,...,g_k$ are functions over disjoint sets of variables satisfying the conjecture, and if the Fourier transform of $F$ taken with respect to the product distribution with biases $E[g_1],...,E[g_k]$ satisfies the conjecture, then their composition $F(g_1(x^1),...,g_k(x^k))$ satisfies the conjecture. As an application we show that the FEI conjecture holds for read-once formulas over arbitrary gates of bounded arity, extending a recent result [OWZ11] which proved it for read-once decision trees. Our techniques also yield an explicit function with the largest known ratio of $C \geq 6.278$ between $H[f]$ and $Inf[f]$, improving on the previous lower bound of 4.615.
Consider a finite irreducible Markov chain with invariant distribution $π$. We use the inner product induced by $π$ and the associated heat operator to simplify and generalize some results related to graph partitioning and the small-set expansion problem. For example, Steurer showed a tight connection between the number of small eigenvalues of a graph's Laplacian and the expansion of small sets in that graph. We give a simplified proof which generalizes to the nonregular, directed case. This result implies an approximation algorithm for an "analytic" version of the Small-Set Expansion Problem, which, in turn, immediately gives an approximation algorithm for Small-Set Expansion. We also give a simpler proof of a lower bound on the probability that a random walk stays within a set; this result was used in some recent works on finding small sparse cuts.
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.
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" (SOS) proofs, a powerful algebraic proof system introduced in 1999 by Grigoriev and Vorobjov. Work of Shor, Lasserre, and Parrilo shows that this proof system 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 solved close to optimally 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?
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 instance of the 2-to-1 Label Cover problem, it is NP-hard to find a $(23/24 + \eps)$-satisfying assignment.
A list of open problems in the field of analysis of boolean functions, compiled February 2012 for the Simons Symposium.
Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper we prove two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in $\R^n \times \{-1,1\}.$ We prove that for any constants $d\geq 1, \eps > 0$, {itemize} Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a degree-$d$ PTF that is consistent with a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a degree-$d$ PTF that is consistent with a $1-\eps$ fraction of the examples. It is $\NP$-hard to find a degree-2 PTF that is consistent with a $(\half + \eps)$ fraction of a given set of labeled examples in $\R^n \times \{-1,1\}$, even if there exists a halfspace (degree-1 PTF) that is consistent with a $1 - \eps$ fraction of the examples. {itemize} These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-$d$ PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-2 PTFs and agnostically learns halfspaces (i.e. degree-1 PTFs) under arbitrary distributions.
Consider an optimization problem with $n$ binary variables and $d+1$ linear objective functions. Each valid solution $x \in \{0,1\}^n$ gives rise to an objective vector in $\R^{d+1}$, and one often wants to enumerate the Pareto optima among them. In the worst case there may be exponentially many Pareto optima; however, it was recently shown that in (a generalization of) the smoothed analysis framework, the expected number is polynomial in $n$. Unfortunately, the bound obtained had a rather bad dependence on $d$; roughly $n^{d^d}$. In this paper we show a significantly improved bound of $n^{2d}$. Our proof is based on analyzing two algorithms. The first algorithm, on input a Pareto optimal $x$, outputs a "testimony" containing clues about $x$'s objective vector, $x$'s coordinates, and the region of space $B$ in which $x$'s objective vector lies. The second algorithm can be regarded as a {\em speculative} execution of the first -- it can uniquely reconstruct $x$ from the testimony's clues and just \emph{some} of the probability space's outcomes. The remainder of the probability space's outcomes are just enough to bound the probability that $x$'s objective vector falls into the region $B$.