77 citations · 168 across the 10 of their papers we have counts for
5 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…
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…