Submit good papers to STOC 2004 !

Address:

Oded Regev
583 Soda Hall
EECS Department,
UC Berkeley
Berkeley, CA 94720-1776
Tel: (510) 643-9287

Fax: (510) 642-5775
odedr@ias dót edu

 

Publications (BibTex):

• Randomised Nearest Neighbour Lower Bound, with Amit Chakrabarti, submitted.

• A Lattice Problem in Quantum NP, with Dorit Aharonov, FOCS 2003.

• Universality of Adiabatic Quantum Computation with Two-Body Interactions, with Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau and Seth Lloyd, in preparation.

• New Lattice Based Cryptographic Constructions, STOC 2003.

• Improved Inapproximability of Lattice and Coding Problems with Preprocessing, CCC 2003.

• Vertex Cover might be Hard to Approximate to within 2-\epsilon, with Subhash Khot, CCC 2003.

• 3-Local Hamiltonian is QMA-complete, with Julia Kempe, Quantum Information and Computation.

• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover, with Irit Dinur, Venkatesan Guruswami and Subhash Khot, STOC 2003.

• Long Monotone Paths in Line Arrangements, with J. Balogh, C. Smyth, W. Steiger and M. Szegedy, SOCG 2003.

• The Hardness of Hypergraph Coloring, with Irit Dinur and Clifford Smyth, FOCS 2002

• Quantum Computation and Lattice Problems, FOCS 2002

• Priority Algorithms for Makespan Minimization in the Subset Model, Information Processing Letters

• Temporary Tasks Assignment Resolved
  with A. Armon, Y. Azar, L. Epstein, Proc. of the 13th SODA (2002), 116-124.

• Strongly Polynomial Algorithms for the Unsplittable Flow Problem
  with Y. Azar, Proc. of 8th IPCO (2001), 15-29.

• Maximizing Job Benefits On-line
  with B. Awerbuch and Y. Azar, Proc. of 3rd APPROX (2000), 42-50.

• Off-line Temporary Tasks Assignment
  with Y. Azar, Proc. of 7th ESA (1999), 163-171.

• Minimizing the Flow Time without Migration
  with B. Awerbuch, Y. Azar and S. Leonardi, Proc. of 31st STOC (1999), 198-205.

• On-line Bin-Stretching
  with Y. Azar, Proc. of 2nd. RANDOM (1998), 71-81.