We show that n -bit integers can be factorized by independently running a quantum circuit with \(\tilde{O}(n^{3/2})\) gates for \(\sqrt {n}+4\) times, and then using polynomial-time classical post-processing. The correctness of the algorithm relies on a certain number-theoretic conjecture. It is currently not clear if the algorithm can lead to improved physical implementations in practice.

Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early '80s. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\mathbb{R}^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing—in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime ($k = n^{1-\delta}$). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

We introduce a continuous analogue of the Learning with Errors (LWE) problem, which we name CLWE. We give a polynomial-time quantum reduction from worst-case lattice problems to CLWE, showing that CLWE enjoys similar hardness guarantees to those of LWE. Alternatively, our result can also be seen as opening new avenues of (quantum) attacks on lattice problems. Our work resolves an open problem regarding the computational complexity of learning mixtures of Gaussians without separability assumptions (Diakonikolas 2016, Moitra 2018). As an additional motivation, (a slight variant of) CLWE was considered in the context of robust machine learning (Diakonikolas et al.~FOCS 2017), where hardness in the statistical query (SQ) model was shown; our work addresses the open question regarding its computational hardness (Bubeck et al.~ICML 2019).

We show that for any n-dimensional lattice ℒ ⊆ ℝⁿ, the torus ℝⁿ/ℒ can be embedded into Hilbert space with O(√{nlog n}) distortion. This improves the previously best known upper bound of O(n√{log n}) shown by Haviv and Regev (APPROX 2010, J. Topol. Anal. 2013) and approaches the lower bound of Ω(√n) due to Khot and Naor (FOCS 2005, Math. Ann. 2006).

Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial (nΩ(1)) lower bound for an explicit range counting problem of n3convex polygons in \mathbbR2(each with nÕ̃(1)facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing-in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime (k=n1-δ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

The minrank of a directed graph G is the minimum rank of a matrix M that can be obtained from the adjacency matrix of G by switching some ones to zeros (i.e., deleting edges) and then setting all diagonal entries to one. This quantity is closely related to the fundamental information-theoretic problems of (linear) index coding (Bar-Yossef et al.), network coding (Effros et al.), and distributed storage (Mazumdar, ISIT, 2014). We prove tight bounds on the minrank of directed Erdos- Rényi random graphs G(n, p) for all regimes of p ∈ [0, 1]. In particular, for any constant p, we show that minrk(G) = Θ(n/log n) with high probability, where G is chosen from the previous best lower bound of Ω(√(n)) (Haviv and Langberg), G(n, p). This bound gives a near quadratic improvement over and partially settles an open problem raised by Lubetzky and Stav. Our lower bound matches the well-known upper bound obtained by the “clique covering" solution and settles the linear index coding problem for random knowledge graphs.

We consider the problem of efficiently learning mixtures of a large number of spherical Gaussians, when the components of the mixture are well separated. In the most basic form of this problem, we are given samples from a uniform mixture of k standard spherical Gaussians with means μ1, . . . , μk∈ ℝd, and the goal is to estimate the means up to accuracy δ using poly(k, d, 1/δ) samples. In this work, we study the following question: what is the minimum separation needed between the means for solving this task? The best known algorithm due to Vempala and Wang [JCSS 2004] requires a separation of roughly min{k, d}1/4. On the other hand, Moitra and Valiant [FOCS 2010] showed that with separation o(1), exponentially many samples are required. We address the significant gap between these two bounds, by showing the following results.; We show that with separation o(√(log k)), superpolynomially many samples are required. In fact, this holds even when the k means of the Gaussians are picked at random in d = O(log k) dimensions.; We show that with separation Ω(√(log k)), picked at random in d = O(log k) dimensions. poly(k, d, 1/δ) samples suffice. Notice that the bound on the separation is independent of δ. This result is based on a new and efficient “accuracy boosting” algorithm that takes as input coarse estimates of the true means and in time (and samples) poly(k, d, 1/δ) outputs estimates of the means up to arbitrarily good accuracy δ assuming the separation between the means is Ω(min{√(log k), √d}) (independently of δ). The idea of the algorithm is to iteratively solve a “diagonally dominant” system of non-linear equations. We also (1) present a computationally efficient algorithm in d = O(1) dimensions with only Ω(√d) separation, and (2) extend our results to the case that components might have different weights and variances. These results together essentially characterize the optimal order of separation between components that is needed to learn a mixture of k spherical Gaussians with polynomial samples.

We prove a conjecture due to Dadush, showing that if ℒ⊂ ℝn is a lattice such that det(ℒ′) 1 for all sublattices ℒ′ ⊆ ℒ, then

We give a polynomial-time quantum reduction from worst-case (ideal) lattice problems directly to decision (Ring-)LWE. This extends to decision all the worst-case hardness results that were previously known for the search version, for the same or even better parameters and with no algebraic restrictions on the modulus or number field. Indeed, our reduction is the first that works for decision Ring-LWE with any number field and any modulus.

We show that for any lattice $\mathcal{L} \subseteq \mathbb{R}^n$ and vectors $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$, $\rho(\mathcal{L} + \mathbf{x})^2 \rho(\mathcal{L} + \mathbf{y})^2 \leq \rho(\mathcal{L})^2 \rho(\mathcal{L} + \mathbf{x} + \mathbf{y}) \rho(\mathcal{L} + \mathbf{x} - \mathbf{y}),$ where $\rho$ is the Gaussian mass function $\rho(A) := \sum_{\mathbf{w} \in A} \exp(-\pi \lVert\mathbf{w}\rVert^2)$. We show a number of applications, including bounds on the moments of the discrete Gaussian distribution, various monotonicity properties of the heat kernel on flat tori, and a positive correlation inequality for Gaussian measures on lattices.

We present a natural reverse Minkowski-type inequality for lattices, which gives upper bounds on the number of lattice points in a Euclidean ball in terms of sublattice determinants, and conjecture its optimal form. The conjecture exhibits a surprising wealth of connections to various areas in mathematics and computer science, including a conjecture motivated by integer programming by Kannan and Lovasz (Annals of Math. 1988), a question from additive combinatorics asked by Green, a question on Brownian motions asked by Saloff-Coste (Colloq. Math. 2010), a theorem by Milman and Pisier from convex geometry (Ann. Probab. 1987), worst-case to average-case reductions in lattice-based cryptography, and more. We present these connections, provide evidence for the conjecture, and discuss possible approaches towards a proof. Our main technical contribution is in proving that our conjecture implies the l2 case of the Kannan and Lovasz conjecture. The proof relies on a novel convex relaxation for the covering radius, and a rounding procedure based on "uncrossing" lattice subspaces.

It is well known that Linear Programming is P-complete, with a logspace reduction. In this work we ask whether Linear Programming remains P-complete, even if the polyhedron (i.e., the set of linear inequality constraints) is a fixed polyhedron, for each input size, and only the objective function is given as input. More formally, we consider the following problem: maximize c⋅x, subject to Ax ≤ b; x ∈ Rd, where A,b are fixed in advance and only c is given as an input.

In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).

A matrix A ∊ ℂq×N satisfies the restricted isometry property of order k with constant ∊ if it preserves the ℓ2 norm of all k-sparse vectors up to a factor of 1 ± ∊. We prove that a matrix A obtained by randomly sampling q = O(k · log2 k · log N) rows from an N × N Fourier matrix satisfies the restricted isometry property of order k with a fixed ∊ with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).

We show that for any odd k and any instance I of the max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a 1/2 + Omega(1/sqrt(D)) fraction of I's constraints, where D is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a quantum algorithm to find an assignment satisfying a 1/2 Omega(D^{-3/4}) fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a mu + Omega(1/sqrt(degree)) fraction of constraints, where mu is the fraction that would be satisfied by a uniformly random assignment.

A function defined on the Boolean hypercube is $k$-Fourier-sparse if it has at most $k$ nonzero Fourier coefficients. For a function $f: \mathbb{F}_2^n \rightarrow \mathbb{R}$ and parameters $k$ and $d$, we prove a strong upper bound on the number of $k$-Fourier-sparse Boolean functions that disagree with $f$ on at most $d$ inputs. Our bound implies that the number of uniform and independent random samples needed for learning the class of $k$-Fourier-sparse Boolean functions on $n$ variables exactly is at most $O(n \cdot k \log k)$. As an application, we prove an upper bound on the query complexity of testing Booleanity of Fourier-sparse functions. Our bound is tight up to a logarithmic factor and quadratically improves on a result due to Gur and Tamuz (Chicago J. Theor. Comput. Sci., 2013).

We prove that it is NP-hard to approximate the non-commutative Grothendieck problem to within any constant factor larger than one-half, which matches the approximation ratio of the algorithm of Naor, Regev, and Vidick (STOC'13). Our proof uses an embedding of finite-dimensional Hilbert spaces into the space of matrices endowed with the trace norm with the property that the image of standard basis vectors is longer than that of unit vectors with no large coordinates.

We give a randomized 2n+o(n)-time and space algorithm for solving the Shortest Vector Problem (SVP) on n-dimensional Euclidean lattices. This improves on the previous fastest algorithm: the deterministic ~O(4n)-time and ~O(2n)-space algorithm of Micciancio and Voulgaris (STOC 2010, SIAM J. Comp. 2013). In fact, we give a conceptually simple algorithm that solves the (in our opinion, even more interesting) problem of discrete Gaussian sampling (DGS). More specifically, we show how to sample 2n/2 vectors from the discrete Gaussian distribution at any parameter in 2n+o(n) time and space. (Prior work only solved DGS for very large parameters.) Our SVP result then follows from a natural reduction from SVP to DGS.

We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n/√log n), improving on the previous best of O(n1.5) due to Lag arias, Lenstra, and Schnorr [1]. We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(√n/log n) due to Aharonov and Regev [2]. To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio [3] gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+∈)γ approximate CVP to γ approximate CVP where the target is at distance at most 1+1/∈ times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun [4]. As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice [5]. We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide Ω(√n) factor larger.

We study the Lattice Isomorphism Problem (LIP), in which given two lattices ℒ1 and ℒ2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to ℒ2. Our main result is an algorithm for this problem running in time nO(n) times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of ℤn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.

We show that the Learning with Errors (LWE) problem is classically at least as hard as standard worst-case lattice problems. Previously this was only known under quantum reductions.

The classical Grothendieck inequality has applications to the design of approximation algorithms for NP-hard optimization problems. We show that an algorithmic interpretation may also be given for a noncommutative generalization of the Grothendieck inequality due to Pisier and Haagerup. Our main result, an efficient rounding procedure for this inequality, leads to a constant-factor polynomial time approximation algorithm for an optimization problem which generalizes the Cut Norm problem of Frieze and Kannan, and is shown here to have additional applications to robust principle component analysis and the orthogonal Procrustes problem.

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

We prove an optimal $\Omega(n)$ lower bound on the randomized communication complexity of the much-studied gap-hamming-distance problem. As a consequence, we obtain essentially optimal multipass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments. The gap-hamming-distance problem is a communication problem, wherein Alice and Bob receive $n$-bit strings $x$ and $y$, respectively. They are promised that the Hamming distance between $x$ and $y$ is either at least $n/2+\sqrt{n}$ or at most $n/2-\sqrt{n}$, and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff [Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 283--289], it had been conjectured that the naïve protocol, which uses $n$ bits of communication, is asymptotically optimal. The conjecture was shown to be true in several special cases, e.g., when the communication is deterministic or when the number of rounds of communication is limited. The proof of our aforementioned result, which settles this conjecture fully, is based on a new geometric statement regarding correlations in Gaussian space, related to a result of Borell [Z. Wahrsch. Verw. Gebiete, 70 (1985), pp. 1--13]. To prove this geometric statement, we show that random projections of not-too-small sets in Gaussian space are close to a mixture of translated normal variables.

Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.

We prove an optimal Ω(n) lower bound on the randomized communication complexity of the much-studied Gap-Hamming-Distance problem. As a consequence, we obtain essentially optimal multi-pass space lower bounds in the data stream model for a number of fundamental problems, including the estimation of frequency moments.

In STOC 1999, Raz presented a (partial) function for which there is a quantum protocol communicating only O(log n) qubits, but for which any classical (randomized, bounded-error) protocol requires poly(n) bits of communication. That quantum protocol requires two rounds of communication. Ever since Raz's paper it was open whether the same exponential separation can be achieved with a quantum protocol that uses only one round of communication. Here we settle this question in the affirmative.

We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the parallel repetition question: If the game is played H times in parallel, does the maximum winning probability decay exponentially in ℓ? In the classical setting, this question was answered in the affirmative by Raz. More recently the question arose whether the decay is of the form (1 - ⊖ (ε))ℓwhere 1 - ε is the value of the game and H is the number of repetitions. This question is known as the strong parallel repetition question and was motivated by its connections to the unique games conjecture. It was resolved by Raz who showed that strong parallel repetition does not hold, even in the very special case of games known as XOR games. This opens the question whether strong parallel repetition holds in the case when the provers share entanglement. Evidence for this is provided by the behavior of XOR games, which have strong (in fact perfect) parallel repetition, and by the recently proved strong parallel repetition of linear unique games. A similar question was open for games with so-called non-signaling provers. Here the best known parallel repetition theorem is due to Holenstein, and is of the form (1 - ⊖ (ε2))ℓ. We show that strong parallel repetition holds neither with entangled provers nor with non-signaling provers. In particular we obtain that Holenstein's bound is tight. Along the way we also provide a tight characterization of the asymptotic behavior of the entangled value under parallel repetition of unique games in terms of a semidefinite program.

In this survey we describe the Learning with Errors (LWE) problem, discuss its properties, its hardness, and its cryptographic applications.

We consider the approximate nearest neighbor search problem on the Hamming cube $\{0,1\}^d$. We show that a randomized cell probe algorithm that uses polynomial storage and word size $d^{O(1)}$ requires a worst case query time of $\Omega({\rm log}\,{\rm log}\,d/{\rm log}\,{\rm log}\,{\rm log}\,d)$. The approximation factor may be as loose as $2^{{\rm log}^{1-\eta}d}$ for any fixed $\eta>0$. Our result fills a major gap in the study of this problem since all earlier lower bounds either did not allow randomization [A. Chakrabarti et al., A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, in Discrete and Computational Geometry, Springer, Berlin, 2003, pp. 313–328; D. Liu, Inform. Process. Lett., 92 (2004), pp. 23–29] or did not allow approximation [A. Borodin, R. Ostrovsky, and Y. Rabani, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 312–321; O. Barkol and Y. Rabani, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 388–396; T. S. Jayram et al., J. Comput. System Sci., 69 (2004), pp. 435–447]. We also give a cell probe algorithm that proves that our lower bound is optimal. Our proof uses a lower bound on the round complexity of the related communication problem. We show, additionally, that considerations of bit complexity alone cannot prove any nontrivial cell probe lower bound for the problem. This shows that the “richness technique” [P. B. Miltersen et al., J. Comput. System Sci., 57 (1998), pp. 37–49] used in a lot of recent research around this problem would not have helped here. Our proof is based on information theoretic techniques for communication complexity, a theme that has been prominent in recent research [A. Chakrabarti et al., Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 270–278; Z. Bar-Yossef et al., Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 209–218; P. Sen, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 73–83; R. Jain, J. Radhakrishnan, and P. Sen, Proceedings of the 30th International Colloquium on Automata, Languages and Programming, 2003, pp. 300–315].

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are “unique” constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program (SDP). Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel “quantum rounding technique,” showing how to take a solution to an SDP and transform it into a strategy for entangled provers. Using our approximation by an SDP, we also show a parallel repetition theorem for unique entangled games.

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ( n 2 ) and encrypting a message increases its size by a factor of Õ( n ) (in previous cryptosystems these values are Õ( n 4 ) and Õ( n 2 ), respectively). In fact, under the assumption that all parties share a random bit string of length Õ( n 2 ), the size of the public key can be reduced to Õ( n ).

We study the AprxColoring$(q,Q)$ problem: Given a graph G, decide whether $\chi(G)\le q$ or $\chi(G)\ge Q$. We present hardness results for this problem for any constants $3\le q

We consider the following problem of bounded-error quantum state identification: Given either state $\alpha_0$ or state $\alpha_1$, we are required to output “0”, “1”, or “?” (“don't know"), such that conditioned on outputting “0” or “1”, our guess is correct with high probability. The goal is to maximize the probability of not outputting “?”. We prove the following direct product theorem: If we are given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is $O(ab)$. Our proof is based on semidefinite programming duality. Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with $O(\log n)$ classical bits of communication in the presence of shared randomness, but needs $\Omega(n^{1/3})$ communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Combined with an earlier separation in the other direction due to Bar-Yossef, Jayram, and Kerenidis, this shows that the quantum simultaneous message passing (SMP) model is incomparable with the classical shared-randomness SMP model. Second, we describe a relation that can be computed with $O(\log n)$ classical bits of communication in the presence of shared entanglement, but needs $\Omega((n/\log n)^{1/3})$ communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity of a situation where entanglement buys much more than quantum communication.

Assume Alice and Bob share some bipartite d-dimensional quantum state. A well-known result in quantum mechanics says that by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained locally, i.e., with shared randomness alone. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

We show a connection between the semidefinite relaxation of unique games and their behavior under parallel repetition. Specifically,denoting by val(G) the value of a two-prover unique game G, andby sdpval(G) the value of a natural semidefinite program to approximate val(G), we prove that for every l epsi N, if sdpval(G) ges 1-delta, then val(Gl) ges 1-radicsldelta. Here, Gldenotes the l-fold parallel repetition of G, and s=O(log(k/delta)), where k denotes the alphabet size of the game. For the special case where G is an XOR game (i.e., k=2), we obtain the same bound but with s as an absolute constant. Our bounds on s are optimal up to a factor of O(log(1/delta)). For games with a significant gap between the quantities val(G) and sdpval(G), our result implies that val(Gl) may be much larger than val(G)l, giving a counterexample to the strong parallel repetition conjecture. In a recent breakthrough, Raz (FOCS'08) has shown such an example using the max-cut game on oddcycles. Our results are based on a generalization of his techniques.

The Bonami-Beckner hypercontractive inequality is a powerful tool in Fourier analysis of real-valued functions on the Boolean cube. In this paper we present a version of this inequality for matrix-valued functions on the Boolean cube. Its proof is based on a powerful inequality by Ball, Carlen, and Lieb. We also present a number of applications. First, we analyze maps that encode n classical bits into m qubits, in such a way that each set of k bits can be recovered with some probability by an appropriate measurement on the quantum encoding; we show that if m < 0.7 n, then the success probability is exponentially small in k. This result may be viewed as a direct product version of Nayak's quantum random access code bound. It in turn implies strong direct product theorems for the one-way quantum communication complexity of Disjointness and other problems. Second, we prove that error-correcting codes that are locally decodable with 2 queries require length exponential in the length of the encoded string. This gives what is arguably the first "non-quantum" proof of a result originally derived by Kerenidis and de Wolf using quantum information theory.

We consider one-round games between a classical verifier and two provers who share entanglement. We show that when the constraints enforced by the verifier are `unique' constraints (i.e., permutations), the value of the game can be well approximated by a semidefinite program. Essentially the only algorithm known previously was for the special case of binary answers, as follows from the work of Tsirelson in 1980. Among other things, our result implies that the variant of the unique games conjecture where we allow the provers to share entanglement is false. Our proof is based on a novel `quantum rounding technique', showing how to take a solution to an SDP and transform it to a strategy for entangled provers. Using our approximation by a semidefinite program we also show a parallel repetition theorem for unique entangled games.

Assume Alice and Bob share some bipartite d-dimensional quantum state. As is well known, by performing two-outcome measurements, Alice and Bob can produce correlations that cannot be obtained classically. We show that by using only two bits of communication, Alice and Bob can classically simulate any such correlations. All previous protocols for exact simulation required the communication to grow to infinity with the dimension d. Our protocol and analysis are based on a power series method, resembling Krivine's bound on Grothendieck's constant, and on the computation of volumes of spherical tetrahedra.

We show that unless NP ⊆ RTIME (2poly(log n)), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n-dimensional lattices inthe lp norm (1 ≤q p<∞) to within a factor of 2(log n)1-ε. This improves the previous best factor of 2(logn)1/2-ε under the same complexity assumption due to Khot. Under the stronger assumption NP ࣰ RSUBEXP, we obtain a hardness factor of nc/log log n for some c > 0.

Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power was unknown. We describe an efficient adiabatic simulation of any given quantum algorithm, which implies that the adiabatic computation model and the conventional quantum computation model are polynomially equivalent. Our result can be extended to the physically realistic setting of particles arranged on a two‐dimensional grid with nearest neighbor interactions. The equivalence between the models allows stating the main open problems in quantum computation using well‐studied mathematical objects such as eigenvectors and spectral gaps of sparse matrices.

We show that finding small solutions to random modular linear equations is at least as hard as approximating several lattice problems in the worst case within a factor almost linear in the dimension of the lattice. The lattice problems we consider are the shortest vector problem, the shortest independent vectors problem, the covering radius problem, and the guaranteed distance decoding problem (a variant of the well‐known closest vector problem). The approximation factor we obtain is $n \log^{O(1)} n$ for all four problems. This greatly improves on all previous work on the subject starting from Ajtai’s seminal paper [Generating hard instances of lattice problems, in Complexity of Computations and Proofs, Quad. Mat. 13, Dept. Math., Seconda Univ. Napoli, Caserta, Italy, 2004, pp. 1–32] up to the strongest previously known results by Micciancio [SIAM J. Comput., 34 (2004), pp. 118–169]. Our results also bring us closer to the limit where the problems are no longer known to be in NP intersect coNP. Our main tools are Gaussian measures on lattices and the high‐dimensional Fourier transform. We start by defining a new lattice parameter which determines the amount of Gaussian noise that one has to add to a lattice in order to get close to a uniform distribution. In addition to yielding quantitatively much stronger results, the use of this parameter allows us to simplify many of the complications in previous work. Our technical contributions are twofold. First, we show tight connections between this new parameter and existing lattice parameters. One such important connection is between this parameter and the length of the shortest set of linearly independent vectors. Second, we prove that the distribution that one obtains after adding Gaussian noise to the lattice has the following interesting property: the distribution of the noise vector when conditioning on the final value behaves in many respects like the original Gaussian noise vector. In particular, its moments remain essentially unchanged.

We provide the first hardness result for the covering radius problem on lattices (CRP). Namely, we show that for any large enough p les infin there exists a constant cp> 1 such that CRP in the lscrpnorm is Pi2-hard to approximate to within any constant less than cp. In particular, for the case p = infin, we obtain the constant Cinfin= 1.5. This gets close to the constant 2 beyond which the problem is not believed to be Pi2-hard. As part of our proof, we establish a stronger hardness of approximation result for the forallexist-3-SAT problem with bounded occurrences. This hardness result might be useful elsewhere

We study the APPROXCOLORING q(Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q. We derive conditional hardness for this problem for any constant 3 ≤ q < Q. For q ≥ 4, our result is based on Khot's 2-to-1 conjecture [Khot'02]. For q=3, we base our hardness result on a certain 'fish shaped' variant of his conjecture.We also prove that the problem ALMOST-3-COLORINGε is hard for any constant ε>0, assuming Khot's Unique Games conjecture. This is the problem of deciding for a given graph, between the case where one can 3-color all but a ε fraction of the vertices without monochromatic edges, and the case where the graph contains no independent set of relative size at least ε.Our result is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05].

We consider the problem of bounded-error quantum state identification: given either state α0 or state α1, we are required to output '0', '1' or 'DONO' ("don't know"), such that conditioned on outputting '0' or '1', our guess is correct with high probability. The goal is to maximize the probability of not outputting 'DONO'. We prove a direct product theorem: if we're given two such problems, with optimal probabilities a and b, respectively, and the states in the first problem are pure, then the optimal probability for the joint bounded-error state identification problem is O(ab). Our proof is based on semidefinite programming duality and may be of wider interest.Using this result, we present two exponential separations in the simultaneous message passing model of communication complexity. First, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs Ω(n1/3) communication if the parties don't share randomness, even if communication is quantum. This shows the optimality of Yao's recent exponential simulation of shared-randomness protocols by quantum protocols without shared randomness. Second, we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs Ω((n/log n)1/3) communication if the parties share randomness but no entanglement, even if communication is quantum. This is the first example in communication complexity where entanglement buys you much more than quantum communication does.

We present reductions from lattice problems in the l2 norm to the corresponding problems in other norms such as l1, l∞ (and in fact in any other lp norm where 1 ≤ p ≤ ∞). We consider lattice problems such as the Shortest Vector Problem, Shortest Independent Vector Problem, Closest Vector Problem and the Closest Vector Problem with Preprocessing. Most reductions are simple and follow from known constructions of embeddings of normed spaces.Among other things, our reductions imply that the Shortest Vector Problem in the l1 norm and the Closest Vector Problem with Preprocessing in the l∞ norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2-ε, while no hardness result was known for the latter problem.

The k-{\locHam} problem is a natural complete problem for the complexity class $\QMA$, the quantum analogue of $\NP$. It is similar in spirit to {\sc MAX-k-SAT}, which is $\NP$-complete for $k\geq 2$. It was known that the problem is $\QMA$-complete for any $k \geq 3$. On the other hand, 1-{\locHam} is in {\P} and hence not believed to be $\QMA$-complete. The complexity of the 2-{\locHam} problem has long been outstanding. Here we settle the question and show that it is $\QMA$-complete. We provide two independent proofs; our first proof uses only elementary linear algebra. Our second proof uses a powerful technique for analyzing the sum of two Hamiltonians; this technique is based on perturbation theory and we believe that it might prove useful elsewhere. Using our techniques we also show that adiabatic computation with 2-local interactions on qubits is equivalent to standard quantum computation.

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).

We initiate the study of the computational complexity of the covering radius problem for lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices. For the covering radius on n-dimensional lattices, we show that the problem can be approximated within any constant factor γ(n) > 1 in random exponential time 2 O(n). We also prove that suitably defined gap versions of the problem lie in AM for λ(n) = 2, in coAM for $$ \gamma (n) = {\sqrt {n/\log n} }, $$ and in NP ∩ coNP for $$ \gamma (n) = {\sqrt n }. $$ For the covering radius on n-dimensional linear codes, we show that the problem can be solved in deterministic polynomial time for approximation factor $$ \gamma (n) = \log n, $$ but cannot be solved in polynomial time for some $$ \gamma (n) = \Omega (\log \log n) $$ unless NP can be simulated in deterministic $$ n^{{O(\log \log \log n)}} $$ time. Moreover, we prove that the problem is NP-hard for any constant approximation factor, it is Π2-hard for some constant approximation factor, and that it is unlikely to be Π2-hard for approximation factors larger than 2 (by giving an AM protocol for the appropriate gap problem). This is a natural hardness of approximation result in the polynomial hierarchy. For the shortest independent vectors problem, we give a coAM protocol achieving approximation factor $$ \gamma (n) = {\sqrt {n/\log n} }, $$ solving an open problem of Blömer and Seifert (STOC’99), and prove that the problem is also in coNP for $$ \gamma (n) = {\sqrt n }. $$ Both results are obtained by giving a gap-preserving nondeterministic polynomial time reduction to the closest vector problem.

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of √n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk [1993], Goldreich and Goldwasser [2000], and Aharonov and Regev [2003]. Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier series over the lattice. This technique might be useful elsewhere---we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP) improving on a previous result of Regev[2003]. An interesting fact is that our result emerged from a “dequantization” of our previous quantum result in Aharonov and Regev [2003]. This route to proving purely classical results might be beneficial elsewhere.

Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyperedge. We present a new multilayered probabilistically checkable proof (PCP) construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within a factor of $(k-1-\epsilon)$ for arbitrary constants $\epsilon>0$ and $k\ge 3$. The result is nearly tight as this problem can be easily approximated within factor k. Our construction makes use of the biased long-code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets. We also give a different proof that shows an inapproximability factor of $\lfloor \frac{k}{2} \rfloor -\eps$. In addition to being simpler, this proof also works for superconstant values of k up to (log N) 1/c , where c > 1 is a fixed constant and N is the number of hyperedges.

We initiate the study of the computational complexity of the covering radius problem for point lattices, and approximation versions of the problem for both lattices and linear codes. We also investigate the computational complexity of the shortest linearly independent vectors problem, and its relation to the covering radius problem for lattices. For the covering radius on n-dimensional lattices, we show that the problem can be approximated within any constant factor /spl gamma/(n) > 1 in random exponential time 2/sup O(n)/, it is in AM for /spl gamma/(n) = 2, in coAM for /spl gamma/(n) = /spl radic/(n log n), and in NP /spl cap/ coNP for /spl gamma/(n) = /spl radic/n. For the covering radius on n-dimensional linear codes, we show that the problem can be solved in deterministic polynomial time for approximation factor /spl gamma/(n) = log n, but cannot be solved in polynomial time for some /spl gamma/(n) = /spl Omega/(log log n) unless NP can be simulated in deterministic n/sup O(log log log n)/ time. Moreover, we prove that the problem is NP-hard for every constant approximation factor, it is /spl Pi//sub 2/-hard for some constant approximation factor, and it is in AM for approximation factor 2. So, it is unlikely to be /spl Pi//sub 2/-hard for approximation factors larger than 2. This is a natural hardness of approximation result in the polynomial hierarchy. For the shortest independent vectors problem, we give a coAM protocol achieving approximation factor /spl gamma/(n) = /spl radic/(n/log n), solving an open problem of Blomer and Seifert (1999), and prove that the problem is also in coNP for /spl gamma/(n) = /spl radic/n. Both results are obtained by giving a gap-preserving nondeterministic polynomial time reduction to the closest vector problem.

The model of adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its exact computational power has been unknown. We settle this question and describe an efficient adiabatic simulation of any given quantum algorithm. This implies that the adiabatic computation model and the standard quantum circuit model are polynomially equivalent. We also describe an extension of this result with implications to physical implementations of adiabatic computation. We believe that our result highlights the potential importance of the adiabatic computation model in the design of quantum algorithms and in their experimental realization.

We show that the problems of approximating the shortest and closest vector in a lattice to within a factor of /spl radic/n lie in NP intersect coNP. The result (almost) subsumes the three mutually-incomparable previous results regarding these lattice problems: Banaszczyk (1993), Goldreich and Goldwasser (2000), and Aharonov and Regev (2003). Our technique is based on a simple fact regarding succinct approximation of functions using their Fourier transform over the lattice. This technique might be useful elsewhere - we demonstrate this by giving a simple and efficient algorithm for one other lattice problem (CVPP,) improving on a previous result of Regev (2003). An interesting fact is that our result emerged from a "dequantization" of our previous quantum result in (Aharanov and Regev, 2003). This route to proving purely classical results might be beneficial elsewhere.

We consider the approximate nearest neighbour search problem on the Hamming cube {0, 1 }/sup d/. We show that a randomised cell probe algorithm that uses polynomial storage and word size d/sup O(1)/ requires a worst case query time of /spl Omega/ (log log d/ log log log d). The approximation factor may be as loose as 2/sup log 1 - /spl eta//d for any fixed /spl eta/ > 0. This generalises an earlier result (Chakrabarti et al., 1999) on the deterministic complexity of the same problem and, more importantly, fills a major gap in the study of this problem since all earlier lower bounds either did not allow randomisation according to Chakrabarti et al. (1999) and Liu (2003) or did not allow approximation according to Borodin et al. (1999), Barkol and Rabani (2000), and Jayram et al. (2003). We also give a cell probe algorithm which proves that our lower bound is optimal. Our proof uses a lower bound on the round complexity of the related communication problem. We show, additionally, that considerations of bit complexity alone cannot prove any nontrivial cell probe lower bound for the problem. This shows that the richness technique (Miltersen et al., 1995) used in a lot of research around this problem would not have helped here. Our proof is based on information theoretic techniques for communication complexity, a theme that has been prominent in research by Chakrabarti et al. (2001), Bar-Yossef et al. (2002), Sen (2003) and Jain et al. (2003). In particular, we make heavy use of the round elimination and message compression ideas in the work of Sen (2003) and Jain et al. (2003), and also introduce a technique which we call message switching.

We show that solving modular linear equation on the average is at least as hard as approximating several lattice problems in the worst case within a factor almost linear in the rank of the lattice. The lattice problems we consider are the shortest vector problem, the shortest independent vectors problem and the covering radius problem. The approximation factor we obtain is O(n) for all three problems. This greatly improves on all previous work on the subject starting from Ajtai's seminal paper (STOC, 1996), up to the strongest previously known results by Micciancio (STOC, 2002). Our results also bring us closer to the limit where the problems are no longer known to be in NP /spl cap/ coNP. Our main tools are Gaussian measures on lattices and the high dimensional Fourier transform. We start by defining a new lattice parameter which determines the amount of Gaussian noise that one has to add to a lattice in order to get close to a uniform distribution, in addition to yielding quantitatively much stronger results, the use of this parameter allows us to simplify many of the complications in previous work. Our technical contributions are two-fold. First, we show tight connections between this new parameter and existing lattice parameters. One such important connection is between this parameter and the length of the shortest set of linearly independent vectors. Second, we prove that the distribution that one obtains after adding Gaussian noise to the lattice has the following interesting property: the distribution of the noise vector when conditioning on the final value behaves in many respects like the original Gaussian noise vector. In particular, its moments remain essentially unchanged.

We introduce the use of Fourier analysis on lattices as an integral part of a lattice-based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results ( O ( n 1.5 ) instead of O ( n 7 )). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. Surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). It seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.

We present the first explicit connection between quantum computation and lattice problems. Namely, our main result is a solution to the unique shortest vector problem (SVP) under the assumption that there exists an algorithm that solves the hidden subgroup problem on the dihedral group by coset sampling. Additionally, we present an approach to solving the hidden sub-group problem on the dihedral group by using an average case subset sum routine.

We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within /spl radic/3-/spl epsi/ for any /spl epsi/>0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3-/spl epsi/. These results improve previous results of Feige and Micciancio. We also present the first inapproximability result for the relatively nearest codeword problem with preprocessing (RNCP). Finally, we describe an n-approximation algorithm to CVPP.

Based on a conjecture regarding the power of unique 2-prover-1-round games presented in [S. Khot, (2002)], we show that vertex cover is hard to approximate within any constant factor better than 2. We actually show a stronger result, namely, based on the same conjecture, vertex cover on k-uniform hypergraphs is hard to approximate within any constant factor better than k.

We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within /spl radic/3-/spl epsi/ for any /spl epsi/>0. In addition, we show that the nearest codeword problem with preprocessing (NCPP) is NP-hard to approximate to within 3-/spl epsi/. These results improve the results of Feige and Micciancio (2002). We also present the first inapproximability result for the relatively nearest codeword problem with preprocessing (RNCP). Finally, we describe an n-approximation algorithm to CVPP.

We show how to construct an arrangement of n lines having a monotone path of length O(n2-(d/vlog n)), where d>0 is some constant, and thus nearly settle the long standing question on monotone path length in line arrangements.

We consider coGapSVP/sub /spl radic/n/, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM /spl cap/ coNP but is not known to be in NP or in MA. We prove that it lies inside QMA, the quantum analogue of NP. This is the first non-trivial upper bound on the quantum complexity of a lattice problem. The proof relies on two novel ideas. First, we give a new characterization of QMA, called QMA+ formulation allows us to circumvent a problem which arises commonly in the context of QMA: the prover might use entanglement between different copies of the same state in order to cheat. The second idea involves using estimations of autocorrelation functions for verification. We make the important observation that autocorrelation functions are positive definite functions and using properties of such functions we severely restrict the prover's possibility to cheat. We hope that these ideas will lead to further developments in the field.

Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP construction that extends the Raz verifier. This enables us to prove that Ek-Vertex-Cover is NP-hard to approximate within factor (k-1-ε) for any k ≥ 3 and any ε>0. The result is essentially tight as this problem can be easily approximated within factor k. Our construction makes use of the biased Long-Code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.

We introduce the use of Fourier analysis on lattices as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions around lattice points. Our results include two cryptographic constructions which are based on the worst-case hardness of the unique shortest vector problem. The main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (O(n1.5) instead of O(n7)). This provides the first alternative to Ajtai and Dwork's original 1996 cryptosystem. Our second result is a collision resistant hash function which, apart from improving the security in terms of the unique shortest vector problem, is also the first example of an analysis which is not based on Ajtai's iterative step. Surprisingly, the two results are derived from the same tool which presents two indistinguishable distributions on the segment [0,1]. It seems that this tool can have further applications and as an example we mention how it can be used to solve an open problem related to quantum computation.

We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm (Krivelevich, Nathaniel, and Sudakov, 2001)colors such a graph using O(n/sup 1/5/) colors. Our result immediately implies that for any constants k > 2 and c/sub 2/ > c/sub 1/ > 1, coloring a k-uniform c/sub 1/-colorable hypergraph with c/sub 2/ colors is NP-hard; leaving completely open only the k = 2 graph case. We are the first to obtain a hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k /spl ges/ 4 such a result has been shown by Guruswami et al. (2000), who also discussed the inherent difference between the k = 3 case and k /spl ges/ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph (Kneser, 1955; Lovasz, 1978) and the Schrijver graph (Schrijver, 1978). We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has 'many' non-monochromatic edges.

We present the first explicit connection between quantum computation and lattice problems. Namely, we show a solution to the unique shortest vector problem (SVP) under the assumption that there exists an algorithm that solves the hidden subgroup problem on the dihedral group by coset sampling. Moreover, we solve the hidden subgroup problem on the dihedral group by using an average case subset sum routine. By combining the two results, we get a quantum reduction from /spl Theta//spl tilde/(n/sup 2.5/)-unique-SVP to the average case subset sum problem. This is a better connection than the known classical results.

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (total time in the system). The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption, i.e., interrupt a job and later continue its execution, perhaps migrating it to a different machine. Preemption is inherent to make a scheduling algorithm efficient. While in the case of a single processor most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead. Thus, it is not commonly used in most multiprocessor operating systems. The natural question is whether migration is an inherent component for an efficient scheduling algorithm in either the online or offline setting. Leonardi and Raz [Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, TX, 1997, pp. 110--119] showed that the well-known algorithm, shortest remaining processing time (SRPT), performs within a logarithmic factor of the optimal offline algorithm. Note that SRPT must use both preemption and migration to schedule the jobs. It is not known if better approximation factors can be reached and thus SRPT, although it is an online algorithm, becomes the best known algorithm in the offline setting. In fact, in the online setting, Leonardi and Raz showed that no algorithm can achieve a better bound. Without migration, no (offline or online) approximations are known. This paper introduces a new algorithm that does not use migration, works online, and is just as effective (in terms of approximation ratio) as the best known offline algorithm that uses migration.

We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the flow time (tota time in the system).The performance of the algorithm, both in offline and online settings, can be significantly improved if we allow preemption: i.e., intermpt a job and later continue its execution, perhaps migrating it to a different machine.Preemption is inherent to make a scheduling algorithm efficient.While in case of a single processor, most operating systems can easily handle preemptions, migrating a job to a different machine results in a huge overhead.Thus, it is not commonly used in most multiprocessor operating systems.The natural question is whether migration is an inherent component for an efficient scheduling algorithm, in either online or offline setting.Leonardi and Raz (STOC'97) showed that the well known algorithm, shortest remaining processing time (SRF'I'), performs within a logarithmic factor of the optimal algorithm.Note that SRPT must use both preemption and migration to schedule the jobs.It is not known if better approximation factors can be reached.In fact, in the on-line setting, Leonardi and Raz showed that no algorithm

The POPCORN project provides an infrastructure for globally distributed computation over the whole Internet. It provides any programmer connected to the Internet with a single huge virtual parallel computer composed of all processors on the Internet which care to participate at any given moment. The system provides a market-based mechanism of trade in CPU time to motivate processors to provide their CPU cycles for other peoples' computations. Selling CPU time is as easy as visiting a certain Web site with a Java-enabled browser. Buying CPU time is done by writing a parallel program, using our programming paradigm (and libraries). This paradigm was designed to fit the situation of global computation. A third entity in our system is a market for CPU time, which is where buyers and sellers meet and trade. The system has been implemented and may be visited and used on our Web site: http://www.cs.huji.ac.il/-popcorn.