Abstract. Lattice-based signature schemes following the Goldreich-Goldwasser-Halevi (GGH) design have the unusual property that each signature leaks information on the signer’s secret key, but this...
No Strong Parallel Repetition with Entangled and Non-signaling Provers (2009)
We consider one-round games between a classical verifier and two provers. One of the main questions in this area is the \emph{parallel repetition question}: If the game is played $\ell$ times in...
An optimal randomised cell probe lower bounds for approximate nearest neighbor searching (2009)
Abstract We consider the approximate nearest neighbour search problem on the Hamming Cube {0, 1}d.We show that a randomised cell probe algorithm that uses polynomial storage and word size...
Rounding Parallel Repetitions of Unique Games (2009)
Boaz Barak, Moritz Hardt, Oded Regev, Ishay Haviv, David Steurer, Anup Rao
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, and by...
Rebusco, Paola, Umurhan, Orkan M., Kluzniak, Wlodek, Regev, Oded
Thin viscous Keplerian accretion disks are considered asymptotically stable, even though they can show significant dynamic activity on short timescales. In this paper the dynamics of non-axisymmetric...
NSF grants MSPA-MCS 0528414, and ITR 0205594. (2009)
Boaz Barak, Moritz Hardt, Oded Regev, Ishay Haviv, David Steurer, Anup Rao
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, and by...
Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on trees. In this model...
Vertex Cover Might be Hard to Approximate to (2008)
Abstract Based on a conjecture regarding the power of unique 2-prover-1-round games presented in[Khot02], we show that vertex cover is hard to approximate within any constant factor better than 2. We...
Simultaneous Communication Protocols with Quantum and Classical Messages (2008)
Gavinsky, Dmitry, Regev, Oded, De Wolf, Ronald
We study the simultaneous message passing (SMP) model of communication complexity, for the case where one party is quantum and the other is classical. We show that in an SMP protocol that computes...
On-Line Restricted Assignment of Temporary Tasks with Unknown Durations (2008)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
We consider load balancing of temporary tasks on m machines in the restricted assignment model. It is known that the best competitive ratio for this problem is Θ ( √ m). This bound is not achieved...
Elchanan Mossel, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing (2008)
Kempe, Julia, Regev, Oded, Unger, Falk, De Wolf, Ronald
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of...
Hydrodynamical activity in thin accretion disks (2008)
An asymptotic treatment of thin accretion disks, introduced by Klu\'zniak & Kita (2000) for a steady-state disk flow, is extended to a time-dependent problem. Transient growth of axisymmetric...
Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing (2008)
Julia Kempe, Oded Regev, Falk Unger, Ronald Wolf
We prove new upper bounds on the tolerable level of noise in a quantum circuit. We consider circuits consisting of unitary k-qubit gates each of whose input wires is subject to depolarizing noise of...
The Unique Games Conjecture with Entangled Provers is False (2008)
Kempe, Julia, Regev, Oded, Toner, Ben
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.,...
Lattice-based Cryptography ∗ (2008)
Daniele Micciancio, Oded Regev
In this chapter we describe some of the recent progress in lattice-based cryptography. Lattice-based cryptographic constructions hold a great promise for post-quantum cryptography, as they enjoy very...
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
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...
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
Given a k-uniform hyper-graph, the Ek-Vertex-Cover problem is to nd the minimum-size subset of vertices that `hits ' every hyper-edge. We present a new multilayered PCP construction that extends...
Maximizing Job Benets On-line (2007)
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a benet model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and benet function....
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
We consider the classical problem of scheduling jobs in a multiprocessor setting in order to minimize the ow time (total time in the system). The performance of the algorithm, both in oine and online...
Abstract. We provide the rst strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable ow problem (UFP). In this problem we are given a (possibly...
The Complexity of the Covering Radius Problem on Lattices and Codes (2007)
Venkatesan Guruswami, Daniele Micciancio, Oded Regev
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...
Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E. Steif, Benny Sudakov
In this paper we study the problem of non-interactive correlation distillation (NICD), a generalization of noise sensitivity previously considered in [5, 31, 39]. We extend the model to NICD on...
The Unique Games Conjecture with Entangled Provers is False (2007)
Kempe, Julia, Regev, Oded, Toner, Ben
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.,...
Simulating Quantum Correlations with Finite Communication (2007)
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...
Ben-Aroya, Avraham, Regev, Oded, De Wolf, Ronald
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...
Chaos and complexity in astrophysics (2007)
Methods and techniques of the theory of nonlinear dynamical systems and patterns can be useful in astrophysical applications. Some works on the subjects of dynamical astronomy, stellar pulsation and...
We consider the approximate nearest neighbour search problem on the Hamming cube {0, 1} d. We show that a randomised cell probe algorithm that uses polynomial storage and word size d O(1) requires a...
Yossi Azar, Oded Regev, Presentation Tomer Greenberg, Boris Kapchits
Earlier results Additional problem variations
Lattice problems are known to be hard to approximate to within sub-polynomial factors. For larger approximation factors, such as √ n, lattice problems are known to be in complexity classes such as...
The unique game conjecture with entangled provers is false (2007)
Julia Kempe, Oded Regev, 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.,...
Analytical Methods in CS Instructions as before. Homework 2 (2007)
perfect completeness (i.e., accepts dictatorships with probability 1). 2. Testing resiliency: We call a function f: {0, 1} n → {−1, 1} 1-resilient if � f (S) = 0 for all |S | ≤ 1. (a) Give a...
Analytical Methods in CS Instructions as before. Homework 4 (2007)
1. Learning juntas with queries: Show an algorithm for learning k-juntas in time poly(n, 2 k) using membership queries, without using the Fourier transform. 2. Weakly learning DNFs [1]: Show that if...
Analytical Methods in CS Instructions as before. Homework 3 (2007)
1. The Nisan-Szegedy bound [2]: Let f: {0, 1} n → R be a nonzero function of degree at most d (i.e., ˆ f (S) = 0 for all S of size at least d + 1). (a) Show that Pr [ f (x) � = 0] ≥ 2 −d...
Avraham Ben-aroya, Oded Regev, Ronald 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...
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy (2007)
Ishay Haviv, Oded Regev, Amnon Ta-shma
In 1991, Papadimitriou and Yannakakis gave a reduction implying the NP-hardness of approximating the problem 3-SAT with bounded occurrences [10]. Their reduction is based on expander graphs. We...
Tensor-based hardness of the shortest vector problem to within almost polynomial factors (2007)
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 in the ℓp norm (1...
The Complexity of the Local Hamiltonian Problem (2006)
Kempe, Julia, Kitaev, Alexei, Regev, Oded
The k-LOCAL Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analogue of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k >= 2. It was...
Lattice-based cryptography (2006)
Abstract. We describe some of the recent progress on lattice-based cryptography, starting from the seminal work of Ajtai, and ending with some recent constructions of very efficient cryptographic...
Conditional hardness for approximate coloring (2006)
Irit Dinur, Elchanan Mossel, Oded Regev
We study the APPROXIMATE-COLORING(q, Q) problem: Given a graph G, decide whether χ(G) ≤ q or χ(G) ≥ Q (where χ(G) is the chromatic number of G). We derive conditional hardness for this problem...
Independent sets in graph powers are almost contained in juntas (2006)
Irit Dinur, Ehud Friedgut, Oded Regev
Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...
Independent sets in graph powers are almost contained in juntas (2006)
Irit Dinur, Ehud Friedgut, Oded Regev
Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...
Independent sets in graph powers are almost contained in juntas (2006)
Irit Dinur, Ehud Friedgut, Oded Regev
Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy (2006)
Ishay Haviv, Oded Regev, Amnon Ta-shma
Abstract In 1991, Papadimitriou and Yannakakis gave a reduction implying the NP-hardness of approximatingthe problem 3-SAT with bounded occurrences [10]. Their reduction is based on expander graphs....
Conditional hardness for approximate coloring (2006)
Irit Dinur, Elchanan Mossel, Oded Regev
We study the APPROXIMATE-COLORING(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 ≥...
Dmitry Gavinsky, Julia Kempe, Oded Regev, De Wolf
Abstract. 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 ‘? ’ (“don’t know”),...
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy (2006)
Ishay Haviv, Oded Regev, Amnon Ta-shma
of approximating the problem 3-SAT with bounded occurrences. Their reduction is based on expander graphs. We present an analogue of this result for the second level of the polynomial-time hierarchy...
Gavinsky, Dmitry, Kempe, Julia, Regev, Oded, De Wolf, Ronald
We consider the 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...
Conditional Hardness for Approximate Coloring (2005)
Dinur, Irit, Mossel, Elchanan, Regev, Oded
We study the coloring problem: Given a graph G, decide whether $c(G) \leq q$ or $c(G) \ge Q$, where c(G) is the chromatic number of G. We derive conditional hardness for this problem for any constant...
Closest Vector Problem and the Closest Vector Problem with Preprocessing. The (2005)
We present reductions from lattice problems in the ℓ2 norm to the corresponding problems in other norms such as ℓ1, ℓ ∞ (and in fact in any other ℓp norm where 1 ≤ p ≤ ∞). We consider
On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (2005)
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...
The complexity of the covering radius problem (2005)
Venkatesan Guruswami, Daniele Micciancio, Oded Regev
Abstract. 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...
An Elementary Proof of the Quantum Adiabatic Theorem (2004)
We provide an elementary proof of the quantum adiabatic theorem.
Mossel, Elchanan, O'Donnell, Ryan, Regev, Oded, Steif, Jeffrey, Sudakov, Benjamin
In this paper we study non-interactive correlation distillation (NICD), a generalization of the study of noise sensitivity of boolean functions. We extend the model to NICD on trees. In this model...
The Complexity of the Local Hamiltonian Problem (2004)
Kempe, Julia, Kitaev, Alexei, Regev, Oded
The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analog of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k
In a recent paper, Kuperberg described the first subexponential time algorithm for solving the dihedral hidden subgroup problem. The space requirement of his algorithm is super-polynomial. We...
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (2004)
Aharonov, Dorit, Van Dam, Wim, Kempe, Julia, Landau, Zeph, Lloyd, Seth, Regev, Oded
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...
Worst-case to average-case reductions based on Gaussian measures (2004)
Daniele Micciancio, Oded Regev
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...
Worst-case to average-case reductions based on Gaussian measures (2004)
Daniele Micciancio, Oded Regev
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...
Worst-case to average-case reductions based on Gaussian measures (2004)
Daniele Micciancio, Oded Regev
Abstract 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...
Irit Dinur, Oded Regev, Clifford Smyth
We prove that coloring a 3-uniform 2-colorable hypergraph with c colors is NP-hard for any constant c. The best known algorithm [20] colors such a graph using O(n 1/5) colors. Our result immediately...
Lattice Problems in NP ∩ coNP (2004)
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...
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation (2004)
Adiabatic quantum computation has recently attracted attention in the physics and computer science communities, but its computational power has been unknown. We settle this question and describe an...
The complexity of the local Hamiltonian problem (2004)
Julia Kempe, Alexei Kitaev, Oded Regev
Abstract. The k-local Hamiltonian problem is a natural complete problem for the complexity class QMA, the quantum analogue of NP. It is similar in spirit to MAX-k-SAT, which is NP-complete for k ≥...
New Lattice Based Cryptographic Constructions (2003)
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...
A Lattice Problem in Quantum NP (2003)
We consider coGapSVP_\sqrt{n}, a gap version of the shortest vector in a lattice problem. This problem is known to be in AM\cap coNP but is not known to be in NP or in MA. We prove that it lies...
Launching jets from the boundary layer of accretion disks in young stellar objects (2003)
We reexamine a previously proposed model for thermal pressure acceleration of collimated outflows in young stellar objects (YSO). We are motivated by new results from recent X-ray observations of...
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover (2003)
Dinur, Irit, Guruswami, Venkatesan, Khot, Subhash, Regev, Oded
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...
Quantum Computation and Lattice Problems (2003)
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...
3-Local Hamiltonian is QMA-complete (2003)
It has been shown by Kitaev that the 5-local Hamiltonian problem is QMA-complete. Here we reduce the locality of the problem by showing that 3-local Hamiltonian is already QMA-complete.
New lattice based cryptographic constructions (2003)
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...
A new multilayered PCP and the hardness of hypergraph vertex cover (2003)
Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev
Abstract Given a k-uniform hypergraph, the Ek-Vertex-Cover problem is to find the smallest subsetof vertices that intersects every hyperedge. We present a new multilayered PCP construction that...
New lattice based cryptographic constructions (2003)
Abstract We introduce the use of methods from harmonic analysis as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian...
Improved inapproximability of lattice and coding problems with preprocessing (2003)
We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within p 3 for any > 0. In addition, we show that the nearest codeword problem with preprocessing...
Vertex cover might be hard to approximate to within 2 − ε (2003)
We show that vertex cover is hard to approximate within any constant factor better than 2 where the hardness is based on a conjecture regarding the power of unique 2-prover-1-round games presented in...
New lattice based cryptographic constructions (2003)
We introduce the use of methods from harmonic analysis as an integral part of a lattice based construction. The tools we develop provide an elegant description of certain Gaussian distributions...
Long monotone paths in line arrangements (2003)
Oded Regev, William Steiger, Mario Szegedy
We show how to construct an arrangement of n lines having a monotone path of length n
Quantum Computation and Lattice Problems (2003)
We present the rst explicit connection between quantum computation and lattice problems.
An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching (2003)
We consider the approximate nearest neighbour search problem on the Hamming Cube .
Improved inapproximability of lattice and coding problems with preprocessing (2003)
Abstract We show that the closest vector problem with preprocessing (CVPP) is NP-hard to approximate to within p 3 \Gamma ffl for any ffl? 0. In addition, we show that the nearest codeword problem...
Long monotone paths in line arrangements (2003)
József Balogh, Oded Regev, Clifford Smyth, William Steiger, Mario Szegedy
() N — = #+V ( * () =8-H S () = ()žŸŽi ’=;¡2 ’ ¢ ” £[ ¤ ¥ – œSH( *!Y
Priority algorithms for makespan minimization in the subset model (2002)
We continue the recent study of priority algorithms initiated by Borodin et al. [3]. The denition of a priority algorithm nicely captures the idea of a \greedy-like " type algorithm. While...
Quantum computation and lattice problems (2002)
We present the rst explicit connection between quantum computation and lattice problems. Namely, we show a solution to the unique-SVP under the assumption that there exists an algorithm that solves...
Temporary tasks assignment resolved (2002)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
The hardness of 3-Uniform hypergraph coloring (2002)
We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm [20] colors such a graph using O(n 1=5) colors. Our result...
Off-line Temporary Tasks Assignment (2002)
. In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some...
Temporary Tasks Assignment Resolved (2002)
Amitai Armon, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
Temporary Tasks Assignment Resolved (2002)
Amitai Armon Yossi, Yossi Azar, Leah Epstein, Oded Regev
Among all basic on-line load balancing problems, the only unresolved problem was load balancing of temporary tasks on unrelated machines. This open problem exists for almost a decade, see [Borodin...
Strongly polynomial algorithms for the unsplittable flow problem (2001)
We provide the rst strongly polynomial algorithms with the best approximation ratio for all three variants of the unsplittable ow problem (UFP). In this problem we are given a (possibly directed)...
Baruch Awerbuch, Yossi Azar, Oded Regev
We consider a bene t model for on-line preemptive scheduling. In this model jobs arrive at the on-line scheduler at their release time. Each job arrives with its own execution time and bene t...
Off-line Temporary Tasks Assignment \Lambda (2000)
Yossi Azar, Oded Regev, Gerhard J. Woeginger
Abstract In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and...
Minimizing the flow time without migration (1999)
Baruch Awerbuch, Yossi Azar, Stefano Leonardi, Oded Regev
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...
O-line temporary tasks assignment (1999)
Yossi Azar, Oded Regev, Jir Sgall, Gerhard J. Woeginger
In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some...
Off-line Temporary Tasks Assignment (1999)
Yossi Azar, Oded Regev, Jir Sgall, Gerhard J. Woeginger
In this paper we consider the temporary tasks assignment problem. In this problem, there are m parallel machines and n independent jobs. Each job has an arrival time, a departure time and some...
Minimizing the Flow Time without Migration (1999)
Baruch Awerbuch Yossi, Yossi Azar, Stefano Leonardi, Oded Regev
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...
We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such...
Thermal Equilibria of Accretion Disks (1994)
Abramowicz, Marek A., Chen, Xingming, Kato, Shoji, Lasota, Jean-Pierre, Regev, Oded
We show that most of hot, optically thin accretion disk models which ignore advective cooling are not self-consistent. We have found new types of optically thin disk solutions where cooling is...