If G is a group, we say a subset S of G is product-free if the equation xy=z has no solutions with x,y,z ∈ S.In 1985, Babai and Sós [] asked, for a finite group G, how large a subset S⊆ G can be if it is product-free. The main tool (hitherto) for studying this problem has been the notion of a quasirandom group. For D ∈ ℕ, a group G is said to be D-quasirandom if the minimal dimension of a nontrivial complex irreducible representation of G is at least D. Gowers showed that in a D-quasirandom finite group G, the maximal size of a product-free set is at most |G|/D1/3. This disproved a longstanding conjecture of Babai and Sós from 1985. For the special unitary group, G=(n), Gowers observed that his argument yields an upper bound of n−1/3 on the measure of a measurable product-free subset. In this paper, we improve Gowers’ upper bound to exp(−cn1/3), where c>0 is an absolute constant. In fact, we establish something stronger, namely, product-mixing for measurable subsets of (n) with measure at least exp(−cn1/3); for this product-mixing result, the n1/3 in the exponent is sharp. Our approach involves introducing novel hypercontractive inequalities, which imply that the non-Abelian Fourier spectrum of the indicator function of a small set concentrates on high-dimensional irreducible representations. Our hypercontractive inequalities are obtained via methods from representation theory, harmonic analysis, random matrix theory and differential geometry. We generalize our hypercontractive inequalities from (n) to an arbitrary D-quasirandom compact connected Lie group for D at least an absolute constant, thereby extending our results on product-free sets to such groups. We also demonstrate various other applications of our inequalities to geometry (viz., non-Abelian Brunn-Minkowski type inequalities), mixing times, and the theory of growth in compact Lie groups. A subsequent work due to Arunachalam, Girish and Lifshitz uses our inequalities to establish new separation results between classical and quantum communication complexity.

Abstract It is a classical result that the inner product function cannot be computed by an $${\rm AC}^0$$ AC 0 circuit. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output $$n + n/(\log^{\omega(1)}n)$$ n + n / ( log ω ( 1 ) n ) bits and obtain a tight correlation bound. Our methods extend to many other functions, including pseudorandom functions, and imply a---weak yet nontrivial---limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the above conjecture with the question of learning $${\rm AC}^0$$ AC 0 under simple input distributions.

We prove an analogue of Bonami’s (hypercontractive) lemma for complex-valued functions on L (𝑉 ,𝑊 ), where 𝑉 and 𝑊 are vector spaces over a finite field. This inequality is useful for functions on L (𝑉 ,𝑊 ) whose ‘generalised influences’ are small, in an appropriate sense. It leads to a significant shortening of the proof of a recent seminal result by Khot, Minzer and Safra that pseudorandom sets in Grassmann graphs have near-perfect expansion, which (in combination with the work of Dinur, Khot, Kindler, Minzer and Safra) implies the 2-2 Games conjecture (the variant, that is, with imperfect completeness)

Abstract. Lionel Levine’s hat challenge has [Formula: see text] players, each with a (very large or infinite) stack of hats on their head, each hat independently colored at random black or white. The players are allowed to coordinate before the random colors are chosen, but not after. Each player sees all hats except for those on her own head. They then proceed to simultaneously try and each pick a black hat from their respective stacks. They are proclaimed successful only if they are all correct. Levine’s conjecture is that the success probability tends to zero when the number of players grows. We prove that this success probability is strictly decreasing in the number of players, and present some connections to problems in graph theory: relating the size of the largest independent set in a graph and in a random induced subgraph of it, and bounding the size of a set of vertices intersecting every maximum-size independent set in a graph.

We give alternate proofs for three related results in analysis of Boolean functions, namely the KKL Theorem, Friedgut’s Junta Theorem, and Talagrand’s strengthening of the KKL Theorem. We follow a new approach: looking at the first Fourier level of the function after a suitable random restriction and applying the Log-Sobolev inequality appropriately. In particular, we avoid using the hypercontractive inequality that is common to the original proofs. Our proofs might serve as an alternate, uniform exposition to these theorems and the techniques might benefit further research.

It is a classical result that the inner product function cannot be computed by an AC⁰ circuit [Merrick L. Furst et al., 1981; Miklós Ajtai, 1983; Johan Håstad, 1986]. It is conjectured that this holds even if we allow arbitrary preprocessing of each of the two inputs separately. We prove this conjecture when the preprocessing of one of the inputs is limited to output n + n/(log^{ω(1)} n) bits. Our methods extend to many other functions, including pseudorandom functions, and imply a (weak but nontrivial) limitation on the power of encoding inputs in low-complexity cryptography. Finally, under cryptographic assumptions, we relate the question of proving variants of the main conjecture with the question of learning AC⁰ under simple input distributions.

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −ε, and in the “no” case we show that this fraction is at most ε, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis.

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 accepting states, on average, given an infinite sequence of tosses. We answer this question negatively.

The $k$-fold direct sum encoding of a string $a \in \{0,1\}^n$ is a function $f_a$ that takes as input sets $S \subseteq [n]$ of size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i \pmod 2$. In this paper we prove a direct sum testing theorem. We describe a three query test that accepts with probability one any function of the form $f_a$ for some $a$ and rejects with probability $\Omega(\varepsilon)$ functions $f$ that are $\varepsilon$-far from being a direct sum encoding, where the constant behind the $\Omega$ notation is independent of $k$. This theorem has a couple of additional guises: Linearity testing: By identifying the subsets of $[n]$ with vectors in $\{0,1\}^n$ in the natural way, our result can be thought of as a linearity testing theorem for functions whose domain is restricted to the $k$th layer of the hypercube (i.e., the set of $n$-bit strings with Hamming weight $k$). Tensor power testing: By moving to $-1,1$ notation, the direct sum encoding is equivalent (up to a difference thatis negligible when $k\ll \sqrt n$) to a tensor power. Thus our theorem implies a three query test for deciding if a given tensor $f\in \{-1,1\}^{n^k}$ is a tensor power of a single dimensional vector $a\in \{-1,1\}^n$, i.e., whether there is some $a$ such that $f = a^{\otimes k}$. We also provide a four query test for checking if a given $\pm 1$ matrix has rank $1$. Our test naturally extends the linearity test of Blum, Luby, and Rubinfeld [ J. Comput. Syst. Sci., 47 (1993), pp. 549--595]. Our analysis proceeds by first handling the $k=n/2$ case and then reducing this case to the general $k

To efficiently exploit the network resources operators, do traffic engineering (TE), i.e., adapt the routing of traffic to the prevailing demands. TE in large IP networks typically relies on configuring static link weights and splitting traffic between the resulting shortest paths via the Equal-Cost-MultiPath (ECMP) mechanism. Yet, despite its vast popularity, crucial operational aspects of TE via ECMP are still little-understood from an algorithmic viewpoint. We embark upon a systematic algorithmic study of TE with ECMP. We consider the standard model of TE with ECMP and prove that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat, settling a long-standing open question. We establish, in contrast, that ECMP can provably achieve optimal traffic flow for the important category of Clos datacenter networks. We last consider a well-documented shortcoming of ECMP: suboptimal routing of large (“elephant”) flows. We present algorithms for scheduling “elephant” flows on top of ECMP (as in, e.g., Hedera) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

We develop a polynomial time Ω ( log R) approximate algorithm for Max 2CSP-R, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size R, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a 1/R-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming. The Semidefinite Program that we use has an almost-matching integrality gap. For the more general Max kCSP-R, in which each constraint involves k variables, each ranging over a set of size R, it was known that the best possible approximation is of the order of k/Rk – 1, provided that k is sufficiently large compared to R; our algorithm shows that the bound k/Rk – 1 is not tight for k = 2.

The k-fold direct sum encoding of a string α ∈ --0,1}n is a function fα that takes as input sets S ⊆ [n] of size k and outputs fα (S) = ∑i ∈ S αi (mod 2. In this paper we prove a Direct Sum Testing theorem. We describe a three query test that accepts with probability one any function of the form fα for some α, and rejects with probability Ω(ε) functions f that are ε being a direct sum encoding.

We show that every language in NP has a PCP verifier that tosses O(log n) random coins, has perfect completeness, and a soundness error of at most 1/poly(n), while making O(poly log log n) queries into a proof over an alphabet of size at most n1/poly log log n. Previous constructions that obtain 1/poly(n) soundness error used either poly log n queries or an exponential alphabet, i.e. of size 2nc for some c> 0. Our result is an exponential improvement in both parameters simultaneously. Our result can be phrased as polynomial-gap hardness for approximate CSPs with arity poly log log n and alphabet size n1/poly log n. The ultimate goal, in this direction, would be to prove polynomial hardness for CSPs with constant arity and polynomial alphabet size (aka the sliding scale conjecture for inverse polynomial soundness error).

To efficiently exploit network resources operators do traffic engineering (TE), i.e., adapt the routing of traffic to the prevailing demands. TE in large IP networks typically relies on configuring static link weights and splitting traffic between the resulting shortest-paths via the Equal-Cost-MultiPath (ECMP) mechanism. Yet, despite its vast popularity, crucial operational aspects of TE via ECMP are still little-understood from an algorithmic viewpoint. We embark upon a systematic algorithmic study of TE with ECMP. We consider the standard model of TE with ECMP and prove that, in general, even approximating the optimal link-weight configuration for ECMP within any constant ratio is an intractable feat, settling a long-standing open question. We establish, in contrast, that ECMP can provably achieve optimal traffic flow for the important category of Clos datacenter networks. We last consider a well-documented shortcoming of ECMP: suboptimal routing of large (“elephant”) flows. We present algorithms for scheduling “elephant” flows on top of ECMP (as in, e.g., Hedera [1]) with provable approximation guarantees. Our results complement and shed new light on past experimental and empirical studies of the performance of TE with ECMP.

This work studies several questions about the optimality of semidefinite programming (SDP) for constraint satisfaction problems (CSPs). First we propose the hypothesis that the well known Basic SDP relaxation is actually optimal for random instances of constraint satisfaction problems for every predicate. This unifies several conjectures proposed in the past, and suggests a unifying principle for the average-case complexity of CSPs. We provide several types of indirect evidence for the truth of this hypothesis, and also show that it (and its variants) imply several conjectures in hardness of approximation including polynomial factor hardness for the densest k subgraph problem and hard instances for the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell (1993).

We study the problem of matrix isomorphism of matrix Lie algebras (MatIsoLie). Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley -- Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set L of matrices that is closed under linear combinations and the operation [A, B] = AB - BA. Two matrix Lie algebras L, L' are matrix isomorphic if there is an invertible matrix M such that conjugating every matrix in L by M yields the set L'. We show that certain cases of MatIsoLie -- for the wide and widely studied classes of semi simple and abelian Lie algebras -- are equivalent to graph isomorphism and linear code equivalence, respectively. On the other hand, we give polynomial-time algorithms for other cases of MatIsoLie, which allow us to mostly derandomize a recent result of Kayal on affine equivalence of polynomials.

This paper strengthens the low-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture. Consider the task of verifying a written proof for the membership of a given input in an NP language. In this paper, this is achieved by making a constant number of accesses to the proof, obtaining error probability that is exponentially small in the total number of bits that are read. We show that the number of bits that are read in each access to the proof can be made as high as log β n , for any constant β < 1, where n is the length of the proof. The BGLR conjecture asserts the same for any constant β, for β smaller or equal to 1. Our results are in fact stronger, implying that the Gap-Quadratic-Solvability problem with a constant number of variables in each equation is NP-hard. That is, given a system of n quadratic equations over a field $${\mathcal{F}}$$ of size up to $$2^{\log^\beta n}$$ , where each equation depends on a constant number of variables, it is NP-hard to distinguish between the case where there is a common solution to all of the equations and the case where any assignment satisfies at most a $${2 / |\mathcal{F}|}$$ fraction of them. At the same time, our proof presents a direct construction of a low-degree test whose error-probability is exponentially small in the number of bits accessed. Such a result was previously known only relying on recursive applications of the entire PCP theorem.

We prove a quantitative version of the Gibbard-Satterthwaite theorem. We show that a uniformly chosen voter profile for a neutral social choice function $f$ of $q \geq 4$ alternatives and $n$ voters will be manipulable with probability at least $10^{-4} \eps^2 n^{-3} q^{-30}$, where $\eps$ is the minimal statistical distance between $f$ and the family of dictator functions. Our results extend those of Fried gut et al, which were obtained for the case of $3$ alternatives, and imply that the approach of masking manipulations behind computational hardness cannot hide manipulations completely. Our proof is geometric. More specifically it extends the method of canonical paths to show that the measure of the profiles that lie on the interface of $3$ or more outcomes is large. To the best of our knowledge our result is the first isoperimetric result to establish interface of more than two bodies.

We present new explicit constructions of deterministic randomness extractors, dispersers and related objects. We say that a distribution X on binary strings of length n is a δ-source if X assigns probability at most 2 −δ n to any string of length n . For every δ>0, we construct the following poly( n )-time computable functions: 2-source disperser: D:({0, 1} n ) 2 → {0, 1} such that for any two independent δ-sources X 1 , X 2 we have that the support of D ( X 1 , X 2 ) is {0, 1}. Bipartite Ramsey graph: Let N =2 n . A corollary is that the function D is a 2-coloring of the edges of K N,N (the complete bipartite graph over two sets of N vertices) such that any induced subgraph of size N δ by N δ is not monochromatic. 3-source extractor: E :({0, 1} n ) 3 → {0, 1} such that for any three independent δ-sources X 1 , X 2 , X 3 we have that E ( X 1 , X 2 , X 3 ) is o (1)-close to being an unbiased random bit. No previous explicit construction was known for either of these for any δ<1/2, and these results constitute significant progress to long-standing open problems. A component in these results is a new construction of condensers that may be of independent interest: This is a function C :{0, 1} n → ({0, 1} n/c ) d (where c and d are constants that depend only on δ) such that for every δ-source X one of the output blocks of C(X) is (exponentially close to) a 0.9-source. (This result was obtained independently by Ran Raz.) The constructions are quite involved and use as building blocks other new and known objects. A recurring theme in these constructions is that objects that were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. The construction of the disperser is based on a new technique which we call “the challenge-response mechanism” that (in some sense) allows “identifying high entropy regions” in a given pair of sources using only one sample from the two sources.

What is the least surface area of a shape that tiles Ropfdunder translations by Zopfd? 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 Ropfdby translations of any full rank discrete lattice Lambda with surface area 2piparV-1parfb, where V is the matrix of basis vectors of Lambda, and par.parfbdenotes 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 Ropfdto rectangular lattice points.

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model, defined by El Gamal in [Open problems presented at the $1984$ workshop on Specific Problems in Communication and Computation sponsored by Bell Communication Research, in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath, eds., Springer-Verlag, New York, 1987, pp. 60–62]. In this model there are $n+1$ processors $P_0,P_1,\ldots,P_n$, each of which is initially given a private input bit $x_i$. The goal is for $P_0$ to learn the value of $f(x_1,\ldots,x_n)$, for some specified function f, using a series of noisy broadcasts. At each step a designated processor broadcasts one bit to all of the other processors, and the bit received by each processor is flipped with fixed probability (independently for each recipient). In 1988, Gallager [IEEE Trans. Inform. Theory, 34 (1988), pp. 176–180] gave a noise-resistant protocol that allows $P_0$ to learn the entire input with constant probability in $O(n\log\log n)$ broadcasts. We prove that Gallager's protocol is optimal, up to a constant factor. Our lower bound follows by reduction from a lower bound for generalized noisy decision trees, a new model which may be of independent interest. For this new model we show a lower bound of $\Omega(n \log n)$ on the depth of a tree that learns the entire input. While the above lower bound is for an n-bit function, we also show an $\Omega(n\log\log n)$ lower bound for the number of broadcasts required to compute certain explicit boolean-valued functions, when the correct output must be attained with probability at least $1-n^{-\alpha}$ for a constant parameter $\alpha>0$ (this bound applies to all threshold functions as well as any other boolean-valued function with linear sensitivity). This bound also follows by reduction from a lower bound of $\Omega(n\log n)$ on the depth of generalized noisy decision trees that compute the same functions with the same error. We also show a (nontrivial) $\Omega(n)$ lower bound on the depth of generalized noisy decision trees that compute such functions with small constant error. Finally, we show the first protocol in the noisy broadcast model that computes the Hamming weight of the input using a linear number of broadcasts.

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 at most 1-(1/m)ldrOmega macr(radicd) (for dlesm2, say). This beats the natural barrier of 1-Theta(1/m)2ldrd for Raz-style proofs and also the SDP bound of Feige-Lovasz; however, it just barely fails to have implications for unique games. On the other hand, we also show that improving our bound would require proving nontrivial lower bounds on the surface area of high-dimensional foams. Specifically, one would need to answer: what is the least surface area of a cell that tiles Rdby the lattice Zd?

In this paper we show a reduction from the Unique Games problem to the problem of approximating MAX‐CUT to within a factor of $\alpha_{\text{\tiny{GW}}} + \epsilon$ for all $\epsilon > 0$; here $\alpha_{\text{\tiny{GW}}} \approx .878567$ denotes the approximation ratio achieved by the algorithm of Goemans and Williamson in [J. Assoc. Comput. Mach., 42 (1995), pp. 1115–1145]. This implies that if the Unique Games Conjecture of Khot in [Proceedings of the 34th Annual ACM Symposium on Theory of Computing, 2002, pp. 767–775] holds, then the Goemans–Williamson approximation algorithm is optimal. Our result indicates that the geometric nature of the Goemans–Williamson algorithm might be intrinsic to the MAX‐CUT problem. Our reduction relies on a theorem we call Majority Is Stablest. This was introduced as a conjecture in the original version of this paper, and was subsequently confirmed in [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30]. A stronger version of this conjecture called Plurality Is Stablest is still open, although [E. Mossel, R. O’Donnell, and K. Oleszkiewicz, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 21–30] contains a proof of an asymptotic version of it. Our techniques extend to several other two‐variable constraint satisfaction problems. In particular, subject to the Unique Games Conjecture, we show tight or nearly tight hardness results for MAX‐2SAT, MAX‐q‐CUT, and MAX‐2LIN(q). For MAX‐2SAT we show approximation hardness up to a factor of roughly $.943$. This nearly matches the $.940$ approximation algorithm of Lewin, Livnat, and Zwick in [Proceedings of the 9th Annual Conference on Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, 2002, pp. 67–82]. Furthermore, we show that our .943... factor is actually tight for a slightly restricted version of MAX‐2SAT. For MAX‐q‐CUT we show a hardness factor which asymptotically (for large q) matches the approximation factor achieved by Frieze and Jerrum [Improved approximation algorithms for MAX k‐CUT and MAX BISECTION, in Integer Programming and Combinatorial Optimization, Springer‐Verlag, Berlin, pp. 1–13], namely $1 - 1/q + 2({\rm ln}\,q)/q^2$. For MAX‐2LIN(q) we show hardness of distinguishing between instances which are $(1-\epsilon)$‐satisfiable and those which are not even, roughly, $(q^{-\epsilon/2})$‐satisfiable. These parameters almost match those achieved by the recent algorithm of Charikar, Makarychev, and Makarychev [Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006, pp. 205–214]. The hardness result holds even for instances in which all equations are of the form $x_i - x_j = c$. At a more qualitative level, this result also implies that $1-\epsilon$ vs. ε hardness for MAX‐2LIN(q) is equivalent to the Unique Games Conjecture.

A theorem of Bourgain [4] on Fourier tails states that if f :(-1, 1)n → (-1, 1) is a boolean-valued function on the discrete cube such that for any k > 0, [Σ|S| > k f(S)2 < k-1/2 + o(1), ] then essentially, f depends on only 2O(k) coordinates. This and related theorems such as Friedgut's Theorem [12], KKL [16], the FKN Theorem [14], and the Majority Is Stablest Theorem [27] have proven useful for numerous results in theoretical computer science [3, 5, 9, 6, 7, 10, 11, 18, 19, 20, 24, 17, 25, 23, 22, 28, 29, 31].In this paper we prove an analogue to Bourgain's Theorem for bounded functions on the discrete cube, f : (n ⋺ [-1,1]); such functions arise naturally in hardness-of-approximation problems, as averages of boolean functions. Specifically, we show that for every k > 0, if [Σ|S| > k f(S)2 < exp(-O(k2 log k))] then essentially, f depends on only 2O(k) coordinates. We also show, perhaps surprisingly, that this result is sharp up to the log k factor in the exponent.Our proof uses Fourier analysis, as well as some extremal properties of the Chebyshev polynomials.

We show that, unless NP/spl sube/DTIME(2/sup poly log(n)/) the closest vector problem with pre-processing, for /spl lscr//sub p/ norm for any p /spl ges/ 1, is hard to approximate within a factor of (log n)/sup 1/p - /spl epsi//' /P for any /spl epsi/ > 0. This improves the previous best factor of 3/sup 1/p/ - /spl epsi/ due to Regev (2004). Our results also imply that under the same complexity assumption, the nearest codeword problem with pre-processing is hard to approximate within a factor of (log n)/sup 1 - /spl epsi//' for any /spl epsi/ > 0.

This paper studies the computational complexity of the following type of quadratic programs: given an arbitrary matrix whose diagonal elements are zero, find x /spl isin/ {-1, 1}/sup n/ that maximizes x/sup T/Mx. This problem recently attracted attention due to its application in various clustering settings, as well as an intriguing connection to the famous Grothendieck inequality. It is approximable to within a factor of O(log n), and known to be NP-hard to approximate within any factor better than 13/11 - /spl epsi/ for all /spl epsi/ > 0. We show that it is quasi-NP-hard to approximate to a factor better than O(log/sup /spl gamma// n)for some /spl gamma/ > 0. The integrality gap of the natural semidefinite relaxation for this problem is known as the Grothendieck constant of the complete graph, and known to be /spl Theta/(log n). The proof of this fact was nonconstructive, and did not yield an explicit problem instance where this integrality gap is achieved. Our techniques yield an explicit instance for which the integrality gap is /spl Omega/ (log n/log log n), essentially answering one of the open problems of Alon et al. [AMMN].

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P/sub 0/, P/sub 1/, ..., P/sub n/. Each P/sub i/, for i /spl ges/ 1, initially has a private bit x/sub i/ and the goal is for P/sub 0/ to learn f (x/sub l/, ..., x/sub n/) for some specified function f. At each time step, a designated processor broadcasts some function of its private bit and the bits it has heard so far. Each broadcast is received by the other processors but each reception may be corrupted by noise. In this model, Gallager (1988) gave a noise-resistant protocol that allows P/sub 0/ to learn the entire input in O(n log log n) broadcasts. We prove that Gallager's protocol is optimal up to a constant factor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.

A distribution X over binary strings of length n has min-entropy k if every string has probability at most 2-k in X. We say that X is a δ-source if its rate k⁄n is at least δ.We give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministicextractors, dispersers and related objects. All work for any fixed rate δ>0. No previous explicit construction was known for either of these, for any δ‹1⁄2. The first two constitute major progress to very long-standing open problems.

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.

We answer a question raised by Donald E. Knuth and Andrew C. Yao, concerning the class of polynomials on [0,1] that can be realized as the distribution function of a random variable, whose binary expansion is the output of a finite state automaton driven by unbiased coin tosses. The polynomial distribution functions which can be obtained in this way are precisely those with rational coefficients, whose derivative has no irrational roots on [0,1]. We also show, strengthening a result of Knuth and Yao, that all smooth distribution functions which can be obtained by such automata are polynomials.

We show that a Boolean function over n Boolean variables can be tested for the property of depending on only k of them, using a number of queries that depends only on k and the approximation parameter /spl epsi/. We present two tests, both non-adaptive, that require a number of queries that is polynomial k and linear in /spl epsi//sup -1/. The first test is stronger in that it has a 1-sided error, while the second test has a more compact analysis. We also present an adaptive version and a 2-sided error version of the first test, that have a somewhat better query complexity than the other algorithms. We then provide a lower bound of /spl Omega//spl tilde/(/spl radic/ k) on the number of queries required for the non-adaptive testing of the above property; a lower bound of /spl Omega/(log(k + 1)) for adaptive algorithms naturally follows from this. In providing this we also prove a result about random walks on the group Z/sub 2//sup q/ that may be interesting in its own right. We show that for some t(q) = O/spl tilde/(q/sup 2/), the distributions of the random walk at times t and t + 2 are close to each other, independently of the step distribution of the walk. We also discuss related questions. In particular, when given in advance a known k junta function h, we show how to test a function f for the property of being identical to h up to a permutation of the variables, in a number of queries that is polynomial in k and /spl epsi/.

This paper strengthens the law-error PCP characterization of NP, coming closer to the upper limit of the BGLR conjecture.Namely, we prove that witnesses for membership in any NP language can be verified with a constant nunbcr of accesses, and with an error probability exponentially small in the number of bits accessed, where this number is as high as lagan, for any constant fl < 1. (The BGLR conjecture claims the same for any p 5 1).Our results are in fact stronger, implying the Gap-Quadratic-Solvability problem to be NP-hard even if the equations are restricted to having a constant number of variables.That is, given a system of quadratic-equations over a field 3 (of size up to ZLogD"), where each equation depends on a constant number of variables, it is NP-hard to decide between the case where there is a common solution for all of the equations, and the case where any assignment satisfies no more than a & fraction of them.At the same time, ow proof presents a direct eonstmction of a low-degree-test whose error-probability is expancntially small in the number of hits accessed.Such a result was previously known only relying on recursive applications of the entire PCP theorem.

This paper shows the closest vector in a lattice to be NP-hard to approximate to within any factor up to 2/sup (logn)1-4/ where /spl epsiv/=(loglogn)/sup -c/ for any constant c< 1/2.