603 citations · 1.6k across the 72 of their papers we have counts for
6 papers · 1 filter
New Lattice Based Cryptographic Constructions
Oded Regev
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 di…
A Lattice Problem in Quantum NP
Dorit Aharonov, Oded Regev
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…
Launching jets from the boundary layer of accretion disks in young stellar objects
Noam Soker, Oded Regev
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…
A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
Irit Dinur, Venkatesan Guruswami, Subhash Khot +1
Given a -uniform hyper-graph, the E-Vertex-Cover problem is to find the smallest subset of vertices that intersects every hyper-edge. We present a new multilayered PCP constr…
Quantum Computation and Lattice Problems
Oded Regev
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 assumpti…
3-Local Hamiltonian is QMA-complete
Julia Kempe, Oded Regev
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-comp…