603 citations · 1.6k across the 72 of their papers we have counts for
13 papers · 1 filter
Continuous LWE
Joan Bruna, Oded Regev, Min Jae Song +1
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 CL…
Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors
Ishay Haviv, Oded Regev
$ \newcommand{\SVP}{\mathsf{SVP}} \newcommand{\NP}{\mathsf{NP}} \newcommand{\RTIME}{\mathsf{RTIME}} \newcommand{\RSUBEXP}{\mathsf{RSUBEXP}} \newcommand{\eps}ε \newcommand{\poly}{\m…
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
Ishay Haviv, Oded Regev, Amnon Ta-Shma
$ \newcommand{\eps}ε \newcommand{\NP}{\mathsf{NP}} \newcommand{\YES}{\mathsf{YES}} \newcommand{\NO}{\mathsf{NO}} \newcommand{\myminus}{\text{-}}\newcommand{\Bsat}{\mathsf{B}} \newc…
The Minrank of Random Graphs
Alexander Golovnev, Oded Regev, Omri Weinstein
The minrank of a graph is the minimum rank of a matrix that can be obtained from the adjacency matrix of by switching some ones to zeros (i.e., deleting edges) and then…
Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing
Andris Ambainis, Aleksandrs Belovs, Oded Regev +1
In the -junta testing problem, a tester has to efficiently decide whether a given function is a -junta (i.e., depends on at most of its i…
Beating the random assignment on constraint satisfaction problems of bounded degree
Boaz Barak, Ankur Moitra, Ryan O'Donnell +7
We show that for any odd and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac…