|

|
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.
|