Oded Regev

Vertex cover might be hard to approximate to within<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mn>2</mml:mn><mml:mo>−</mml:mo><mml:mi>ε</mml:mi></mml:math>

Subhash Khot, Oded Regev · Journal of Computer and System Sciences · 2007 · 752 citations

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover

Irit Dinur, Venkatesan Guruswami, Subhash Khot et al. · SIAM Journal on Computing · 2005 · 126 citations

Graph Sparsity, Engineering, Computational Complexity +17

Conditional Hardness for Approximate Coloring

Irit Dinur, Elchanan Mossel, Oded Regev · SIAM Journal on Computing · 2009 · 120 citations

Mathematical Programming, Theory Of Computing, Tight Bounds +14

Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality

Elchanan Mossel, Ryan O’Donnell, Oded Regev et al. · Israel Journal of Mathematics · 2006 · 112 citations

Engineering, Non-interactive Correlation Distillation, Entropy +7

Vertex cover might be hard to approximate to within 2-ε

Subhash Khot, Oded Regev · 2004 · 98 citations

Geometric Graph Theory, Engineering, Graph Theory +14