In this paper we show a reduction from the Unique Games problem to of approximating MAX‐CUT within factor $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here \approx .878567$ denotes approximation ratio achieved by algorithm Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if Conjecture Khot [Proceedings 34th Annual ACM Symposium on Theory Computing, 2002, 767–775] holds, then Goemans–Williamson is optimal. Our result indicates...

In this paper we study functions with low influences on product probability spaces.These are f W 1 n !‫ޒ‬ that have EOEVar i OEf small compared to VarOEf for each .The analysis of boolean 1; 1g !f has become a central problem in discrete Fourier analysis.It is motivated by fundamental questions arising from the construction probabilistically checkable proofs theoretical computer science and problems theory social choice economics.We prove an invariance principle multilinear polynomials...

In the quantum state tomography problem, one wishes to estimate an unknown d-dimensional mixed ρ, given few copies. We show that O(d/ε) copies suffice obtain ρ satisfies ||ρ − ρ||F2 ≤ ε (with high probability). An immediate consequence is O((ρ) · d/ε2) O(d2/ε2) ε-accurate in standard trace distance. This improves on best known prior result of O(d3/ε2) for full tomography, and even O(d2log(d/ε)/ε2) spectrum estimation. Our first nontrivial can be obtained using a number just linear dimension.

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

In this paper, we study functions with low influences on product probability spaces. The analysis of Boolean f {-1, 1}/sup n/ /spl rarr/ 1} has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction probabilistically checkable proofs theoretical computer science and problems theory social choice economics. We prove an invariance principle for multilinear polynomials bounded degree; it shows that under mild conditions...

In this paper, we give evidence suggesting that MAX-CUT is NP-hard to approximate within a factor of /spl alpha//sub cw/+ epsi/, for all epsi/ > 0, where cw/ denotes the approximation ratio achieved by Goemans-Williamson algorithm (1995). ap/ .878567. This result conditional, relying on two conjectures: a) unique games conjecture Khot; and, b) very believable call majority stablest conjecture. These results indicate geometric nature might be intrinsic problem. The same conjectures also imply...

We study the learnability of sets in Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> under Gaussian distribution, taking surface area as "complexity measure" being learned. Let C <sub xmlns:xlink="http://www.w3.org/1999/xlink">S</sub> denote class all (measurable) with at most S. first show that is learnable to any constant accuracy time n xmlns:xlink="http://www.w3.org/1999/xlink">O(S</sup>...

We give an algorithm that learns any monotone Boolean function $\fisafunc$ to constant accuracy, under the uniform distribution, in time polynomial n and decision tree size of $f.$ This is first can learn arbitrary functions high using random examples only, a reasonable measure complexity A key ingredient result new bound showing average sensitivity computed by s must be at most $\sqrt{\log s}$. has proved independent utility study [O. Schramm, R. O'Donnell, M. Saks, Servedio, Every...

We study lower bounds for Locality-Sensitive Hashing (LSH) in the strongest setting: point sets {0,1} d under Hamming distance. Recall that H is said to be an ( r , cr p q )-sensitive hash family if all pairs x y ∈ with dist( ) ≤ have probability at least of collision a randomly chosen h H, whereas {0, 1} ≥ most collision. Typically, one considers → ∞, c &gt; 1 fixed and bounded away from 0. For its applications approximate nearest-neighbor search high dimensions, quality LSH governed by how...

Let P:{0,1}k → {0,1} be a nontrivial k-ary predicate. Consider random instance of the constraint satisfaction problem (P) on n variables with Δ constraints, each being P applied to k randomly chosen literals. Provided density satisfies ≫ 1, such an is unsatisfiable high probability. The refutation efficiently find proof unsatisfiability.

Furthering the study of cryptography in constant parallel time, we give new evidence for security Gold Reich's candidate pseudorandom generator with near-optimal, polynomial stretch. Our consists both against sub exponential-time linear attacks as well using SDP hierarchies such Sherali-Adams+ and Lasserre/Parrilo. More specifically, instantiating 5-ary "Tri-Sum-And" predicate, get a 5-local PRG which is secure based on Lasserre/Parrilo hierarchy. Previous works small locality gave...

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

We present a quantum LDPC code family that has distance Ω(N3/5/polylog(N)) and Θ(N3/5) logical qubits, where N is the length. This first construction achieves greater than N1/2 polylog(N). The based on generalizing homological product of codes to fiber bundle.

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

We prove that for any decision tree calculating a Boolean function f : {-1,1}/sup n/ /spl rarr/ {-1, 1}, Var[f] les/ Sigma/ /sub i=1/ /sup delta//sup i/Inf/sub i/(f), i = 1 where i/ is the probability ith input variable read and Inf/sub i/(f) influence of on f. The variance, are taken with respect to an arbitrary product measure 1}/sup n/n. It follows minimum depth given balanced at least reciprocal largest variable. Likewise, d has 1/d. only previous nontrivial lower bound known was...

This paper addresses the problem of testing whether a Boolean-valued function f is halfspace, i.e., form $f(x)=\mathrm{sgn}(w\cdot x-\theta)$. We consider halfspaces over continuous domain $\mathbf{R}^n$ (endowed with standard multivariate Gaussian distribution) as well Boolean cube $\{-1,1\}^n$ uniform distribution). In both cases we give an algorithm that distinguishes from functions are $\epsilon$-far any halfspace using only $\mathrm{poly}(\frac{1}{\epsilon})$ queries, independent...

In [Proceedings of the Second Symposium on Switching Circuit Theory and Logical Design (FOCS), 1961, pp. 34–38], Chow proved that every Boolean threshold function is uniquely determined by its degree-0 degree-1 Fourier coefficients. These numbers became known as parameters. Providing an algorithmic version Chow's theorem—i.e., efficiently constructing a representation given parameters—has remained open ever since. This problem has received significant study in fields circuit complexity, game...

The Common Core State Standards can be taught with Minecraft, an interactive creative Lego®-like game. Integrating Science, Technology, Engineering, and Mathematics (iSTEM) authors share ideas activities that stimulate student interest in the integrated fields of science, technology, engineering, mathematics (STEM) K—grade 6 classrooms.

We present a range of new results for testing properties Boolean functions that are defined in terms the Fourier spectrum. Broadly speaking, our show property function having concise representation is locally testable. give first efficient algorithms whether has sparse spectrum (small number nonzero coefficients) and supported low-dimensional subspace $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing any algorithm—even an adaptive one—must have query complexity within...