Oded Regev

Proceedings of the Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30, 2010

The Learning with Errors Problem (Invited Survey).

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

No Strong Parallel Repetition with Entangled and Non-signaling Provers.

[BibT_eX]

[DOI]

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

The Euclidean Distortion of Flat Tori.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2010

Learning with Errors over Rings.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Number Theory, 9th International Symposium, 2010

2009

A Note on the Distribution of the Distance from a Lattice.

[BibT_eX]

[DOI]

Vadim Lyubashevsky

Discret. Comput. Geom., 2009

2008

Vertex cover might be hard to approximate to within 2-epsilon.

[BibT_eX]

[DOI]

Subhash Khot

J. Comput. Syst. Sci., 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.

[BibT_eX]

[DOI]

Dmitry Gavinsky

Ronald de Wolf

Chic. J. Theor. Comput. Sci., 2008

Impossibility of a Quantum Speed-Up with a Faulty Oracle.

[BibT_eX]

[DOI]

Liron Schiff

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete.

[BibT_eX]

[DOI]

Lior Eldar

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Unique Games with Entangled Provers are Easy.

[BibT_eX]

[DOI]

Ben Toner

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs.

[BibT_eX]

[DOI]

Avraham Ben-Aroya

Ronald de Wolf

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Rounding Parallel Repetitions of Unique Games.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

Amnon Ta-Shma

Theory Comput., 2007

Tensor-based hardness of the shortest vector problem to within almost polynomial factors.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Simulating Quantum Correlations with Finite Communication.

[BibT_eX]

[DOI]

Ben Toner

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

The Unique Games Conjecture with Entangled Provers is False.

[BibT_eX]

[DOI]

Ben Toner

Proceedings of the Algebraic Methods in Computational Complexity, 07.10. - 12.10.2007, 2007

2006

Combinatorial Algorithms for the Unsplittable Flow Problem.

[BibT_eX]

[DOI]

Algorithmica, 2006

Lattice problems and norm embeddings.

[BibT_eX]

[DOI]

Ricky Rosen

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Bounded-error quantum state identification and exponential separations in communication complexity.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Conditional hardness for approximate coloring.

[BibT_eX]

[DOI]

Irit Dinur

Elchanan Mossel

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.

[BibT_eX]

[DOI]

Phong Q. Nguyen

Proceedings of the Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28, 2006

Lattice-Based Cryptography.

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology, 2006

Hardness of the Covering Radius Problem on Lattices.

[BibT_eX]

[DOI]

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

The complexity of the covering radius problem.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Daniele Micciancio

Comput. Complex., 2005

On lattices, learning with errors, random linear codes, and cryptography.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

The Complexity of the Local Hamiltonian Problem.

[BibT_eX]

[DOI]

Alexei Y. Kitaev

Proceedings of the FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science, 2004

Worst-Case to Average-Case Reductions Based on Gaussian Measures.

[BibT_eX]

[DOI]

Daniele Micciancio

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching.

[BibT_eX]

[DOI]

Amit Chakrabarti

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

Lattice Problems in NP cap coNP.

[BibT_eX]

[DOI]

Dorit Aharonov

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

The Complexity of the Covering Radius Problem on Lattices and Codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Daniele Micciancio

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

3-local Hamiltonian is QMA-complete.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2003

On-line restricted assignment of temporary tasks with unknown durations.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2003

New lattice based cryptographic constructions.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A new multilayered PCP and the hardness of hypergraph vertex cover.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A Lattice Problem in Quantum NP.

[BibT_eX]

[DOI]

Dorit Aharonov

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Long monotone paths in line arrangements.

[BibT_eX]

[DOI]

Proceedings of the 19th ACM Symposium on Computational Geometry, 2003

Improved Inapproximability of Lattice and Coding Problems with Preprocessing.

[BibT_eX]

[DOI]

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

Vertex Cover Might be Hard to Approximate to within 2-\varepsilon.

[BibT_eX]

[DOI]

Subhash Khot

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Off-line temporary tasks assignment.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2002

Priority algorithms for makespan minimization in the subset model.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2002

Temporary tasks assignment resolved.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Quantum Computation and Lattice Problems.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

The Hardness of 3 - Uniform Hypergraph Coloring.

[BibT_eX]

[DOI]

Irit Dinur

Clifford D. Smyth

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Scheduling and load balancing

[BibT_eX]

[DOI]

PhD thesis, 2001

Strongly Polynomial Algorithms for the Unsplittable Flow Problem.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Maximizing job benefits on-line.

[BibT_eX]

[DOI]

Baruch Awerbuch

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Minimizing the Flow Time Without Migration.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Off-Line Temporary Tasks Assignment.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1999

1998

On-Line Bin-Stretching.

[BibT_eX]

[DOI]