Oded Regev 0001

STOC Conference 2021 Conference Paper

Continuous LWE

• Joan Bruna
• Oded Regev 0001
• Min Jae Song
• Yi Tang 0012

FOCS Conference 2020 Conference Paper

Polynomial Data Structure Lower Bounds in the Group Model

• Alexander Golovnev
• Gleb Posobin
• Oded Regev 0001
• Omri Weinstein

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 n 3 convex polygons in \mathbbR 2 (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=n 1-δ ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.

STOC Conference 2017 Conference Paper

A reverse Minkowski theorem

• Oded Regev 0001
• Noah Stephens-Davidowitz

We prove a conjecture due to Dadush, showing that if ℒ⊂ ℝ n is a lattice such that det(ℒ′) 1 for all sublattices ℒ′ ⊆ ℒ, then $$\sum_{ y ∈ℒ}^e -t 2||y||2 ≤3/2,$$ where t := 10(logn + 2). From this we also derive bounds on the number of short lattice vectors and on the covering radius.

FOCS Conference 2017 Conference Paper

On Learning Mixtures of Well-Separated Gaussians

• Oded Regev 0001
• Aravindan Vijayaraghavan

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.

STOC Conference 2017 Conference Paper

Pseudorandomness of ring-LWE for any ring and modulus

• Chris Peikert
• Oded Regev 0001
• Noah Stephens-Davidowitz

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.

SODA Conference 2016 Conference Paper

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

• Andris Ambainis
• Aleksandrs Belovs
• Oded Regev 0001
• Ronald de Wolf

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 Ω( k 1/3 ) queries for junta-testing (for constant ∊ ).

SODA Conference 2016 Conference Paper

The Restricted Isometry Property of Subsampled Fourier Matrices

• Ishay Haviv
• Oded Regev 0001

FOCS Conference 2016 Conference Paper

Towards Strong Reverse Minkowski-Type Inequalities for Lattices

• Daniel Dadush
• Oded Regev 0001

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.

STOC Conference 2015 Conference Paper

Solving the Shortest Vector Problem in 2 n Time Using Discrete Gaussian Sampling: Extended Abstract

• Divesh Aggarwal
• Daniel Dadush
• Oded Regev 0001
• Noah Stephens-Davidowitz

We give a randomized 2 n+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(4 n )-time and ~O(2 n )-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 2 n/2 vectors from the discrete Gaussian distribution at any parameter in 2 n+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. In addition, we give a more refined algorithm for DGS above the so-called smoothing parameter of the lattice, which can generate 2 n/2 discrete Gaussian samples in just 2 n/2+o(n) time and space. Among other things, this implies a 2 n/2+o(n) -time and space algorithm for 1.93-approximate decision SVP.

FOCS Conference 2015 Conference Paper

Tight Hardness of the Non-commutative Grothendieck Problem

• Jop Briët
• Oded Regev 0001
• Rishi Saket

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.

SODA Conference 2014 Conference Paper

On the Lattice Isomorphism Problem

• Ishay Haviv
• Oded Regev 0001

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 L 1 to ℒ 2. Our main result is an algorithm for this problem running in time n O ( 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.

STOC Conference 2013 Conference Paper

Classical hardness of learning with errors

• Zvika Brakerski
• Adeline Langlois
• Chris Peikert
• Oded Regev 0001
• Damien Stehlé

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. Our techniques capture the tradeoff between the dimension and the modulus of LWE instances, leading to a much better understanding of the landscape of the problem. The proof is inspired by techniques from several recent cryptographic constructions, most notably fully homomorphic encryption schemes.

STOC Conference 2013 Conference Paper

Efficient rounding for the noncommutative grothendieck inequality

• Assaf Naor
• Oded Regev 0001
• Thomas Vidick

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.

STOC Conference 2011 Conference Paper

An optimal lower bound on the communication complexity of gap-hamming-distance

• Amit Chakrabarti
• Oded Regev 0001

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. 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+√n or at most n/2-√n, and their goal is to decide which of these is the case. Since the formal presentation of the problem by Indyk and Woodruff (FOCS, 2003), it had been conjectured that the naive 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 C. Borell (1985). 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.

STOC Conference 2011 Conference Paper

Quantum one-way communication can be exponentially stronger than classical communication

• Oded Regev 0001
• Bo'az Klartag

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.

FOCS Conference 2008 Conference Paper

A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs

• Avraham Ben-Aroya
• Oded Regev 0001
• Ronald de Wolf

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.

FOCS Conference 2008 Conference Paper

Rounding Parallel Repetitions of Unique Games

• Boaz Barak
• Moritz Hardt
• Ishay Haviv
• Anup Rao 0001
• Oded Regev 0001
• David Steurer

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(G l ) ges 1-radicsldelta. Here, G l denotes 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(G l ) 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.

FOCS Conference 2008 Conference Paper

Unique Games with Entangled Provers are Easy

• Julia Kempe
• Oded Regev 0001
• Ben Toner

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.

FOCS Conference 2007 Conference Paper

Simulating Quantum Correlations with Finite Communication

• Oded Regev 0001
• Ben Toner

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.

STOC Conference 2007 Conference Paper

Tensor-based hardness of the shortest vector problem to within almost polynomial factors

• Ishay Haviv
• Oded Regev 0001

We show that unless NP ⊆ RTIME (2 poly(log n) ), for any ε > 0 there is no polynomial-time algorithm approximating the Shortest Vector Problem (SVP) on n -dimensional lattices inthe l p norm (1 ≤q p 0.

STOC Conference 2006 Conference Paper

Bounded-error quantum state identification and exponential separations in communication complexity

• Dmitry Gavinsky
• Julia Kempe
• Oded Regev 0001
• Ronald de Wolf

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 Ω(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. 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.

STOC Conference 2006 Conference Paper

Conditional hardness for approximate coloring

• Irit Dinur
• Elchanan Mossel
• Oded Regev 0001

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 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].

STOC Conference 2006 Conference Paper

Lattice problems and norm embeddings

• Oded Regev 0001
• Ricky Rosen

We present reductions from lattice problems in the l 2 norm to the corresponding problems in other norms such as l 1 , l ∞ (and in fact in any other l p 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 l 1 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.

STOC Conference 2005 Conference Paper

On lattices, learning with errors, random linear codes, and cryptography

• Oded Regev 0001

FOCS Conference 2004 Conference Paper

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation

• Dorit Aharonov
• Wim van Dam
• Julia Kempe
• Zeph Landau
• Seth Lloyd
• Oded Regev 0001

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.

FOCS Conference 2004 Conference Paper

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching

• Amit Chakrabarti
• Oded Regev 0001

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.

FOCS Conference 2004 Conference Paper

Lattice Problems in NP cap coNP

• Dorit Aharonov
• Oded Regev 0001

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.

FOCS Conference 2004 Conference Paper

Worst-Case to Average-Case Reductions Based on Gaussian Measures

• Daniele Micciancio
• Oded Regev 0001

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.

FOCS Conference 2003 Conference Paper

A Lattice Problem in Quantum NP

• Dorit Aharonov
• Oded Regev 0001

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.

STOC Conference 2003 Conference Paper

A new multilayered PCP and the hardness of hypergraph vertex cover

• Irit Dinur
• Venkatesan Guruswami
• Subhash Khot
• Oded Regev 0001

Given a k -uniform hyper-graph, the E k -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 E k -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.

STOC Conference 2003 Conference Paper

New lattice based cryptographic constructions

• Oded Regev 0001

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(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 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.

FOCS Conference 2002 Conference Paper

Quantum Computation and Lattice Problems

• Oded Regev 0001

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.

SODA Conference 2002 Conference Paper

Temporary tasks assignment resolved

• Amitai Armon
• Yossi Azar
• Leah Epstein
• Oded Regev 0001

FOCS Conference 2002 Conference Paper

The Hardness of 3 - Uniform Hypergraph Coloring

• Irit Dinur
• Oded Regev 0001
• Clifford D. Smyth

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.

STOC Conference 1999 Conference Paper

Minimizing the Flow Time Without Migration

• Baruch Awerbuch
• Yossi Azar
• Stefano Leonardi 0001
• Oded Regev 0001