77 citations · 168 across the 10 of their papers we have counts for
12 papers
Conditional Hardness for Approximate Coloring
Irit Dinur, Elchanan Mossel, Oded Regev
We study the coloring problem: Given a graph G, decide whether or , where c(G) is the chromatic number of G. We derive conditional hardness for this probl…
Hydrodynamical stability of thin accretion discs: transient growth of global axisymmetric perturbations
O. M. Umurhan, A. Nemirovsky, O. Regev +1
The purpose of this paper is to explore how accretion discs manifest the phenomenon of transient growth on a global scale. We investigate analytically the time response of a thin a…
An Elementary Proof of the Quantum Adiabatic Theorem
Andris Ambainis, Oded Regev
We provide an elementary proof of the quantum adiabatic theorem.
Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
Elchanan Mossel, Ryan O'Donnell, Oded Regev +2
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 tree…
A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
Oded Regev
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-pol…
The Complexity of the Local Hamiltonian Problem
Julia Kempe, Alexei Kitaev, Oded Regev
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…