# Oded Regev

According to our database

Collaborative distances:

^{1}, Oded Regev authored at least 88 papers between 1998 and 2017.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepage:

#### On csauthors.net:

## Bibliography

2017

Tight Hardness of the Non-Commutative Grothendieck Problem.

Theory of Computing, 2017

An Inequality for Gaussians on Lattices.

SIAM J. Discrete Math., 2017

Pseudorandomness of Ring-LWE for Any Ring and Modulus.

IACR Cryptology ePrint Archive, 2017

Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121).

Dagstuhl Reports, 2017

A Sharp Tail Bound for the Expander Random Sampler.

CoRR, 2017

A reverse Minkowski theorem.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

On Learning Mixtures of Well-Separated Gaussians.

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

The List-Decoding Size of Fourier-Sparse Boolean Functions.

TOCT, 2016

The Minrank of Random Graphs.

Electronic Colloquium on Computational Complexity (ECCC), 2016

A Note on Discrete Gaussian Combinations of Lattice Vectors.

Chicago J. Theor. Comput. Sci., 2016

The Restricted Isometry Property of Subsampled Fourier Matrices.

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing.

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

On the Space Complexity of Linear Programming with Preprocessing.

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Towards Strong Reverse Minkowski-Type Inequalities for Lattices.

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Quantum XOR Games.

TOCT, 2015

Recovering Short Generators of Principal Ideals in Cyclotomic Rings.

IACR Cryptology ePrint Archive, 2015

Beating the random assignment on constraint satisfaction problems of bounded degree.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Solving the Shortest Vector Problem in 2

^{n}Time Using Discrete Gaussian Sampling: Extended Abstract.
Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Efficient Rounding for the Noncommutative Grothendieck Inequality.

Theory of Computing, 2014

Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121).

Dagstuhl Reports, 2014

Tight Hardness of the Non-commutative Grothendieck Problem.

CoRR, 2014

Solving the Shortest Vector Problem in $2^n$ Time via Discrete Gaussian Sampling.

CoRR, 2014

On the Lattice Isomorphism Problem.

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On the Closest Vector Problem with a Distance Guarantee.

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

On Ideal Lattices and Learning with Errors over Rings.

J. ACM, 2013

A Toolkit for Ring-LWE Cryptography.

IACR Cryptology ePrint Archive, 2013

Classical hardness of learning with errors.

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors.

Theory of Computing, 2012

Near-Optimal and Explicit Bell Inequality Violations.

Theory of Computing, 2012

Bell violations through independent bases games.

Quantum Information & Computation, 2012

Locally decodable codes and the failure of cotype for projective tensor products

CoRR, 2012

Hardness of the Covering Radius Problem on Lattices.

Chicago J. Theor. Comput. Sci., 2012

2011

Quantum one-way communication can be exponentially stronger than classical communication.

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

On the Complexity of Lattice Problems with Polynomial Approximation Factors.

Proceedings of the LLL Algorithm - Survey and Applications, 2010

Unique Games with Entangled Provers Are Easy.

SIAM J. Comput., 2010

An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching.

SIAM J. Comput., 2010

Upper bounds on the noise threshold for fault-tolerant quantum computing.

Quantum Information & Computation, 2010

Quantum One-Way Communication is Exponentially Stronger Than Classical Communication.

Electronic Colloquium on Computational Complexity (ECCC), 2010

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance.

Electronic Colloquium on Computational Complexity (ECCC), 2010

Lattice Enumeration Using Extreme Pruning.

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

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

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

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

The Euclidean Distortion of Flat Tori.

Proceedings of the Approximation, 2010

Better Gap-Hamming Lower Bounds via Better Round Elimination.

Proceedings of the Approximation, 2010

Learning with Errors over Rings.

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

2009

Simulating Quantum Correlations with Finite Communication.

SIAM J. Comput., 2009

Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity.

SIAM J. Comput., 2009

Learning a Parallelepiped: Cryptanalysis of GGH and NTRU Signatures.

J. Cryptology, 2009

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

J. ACM, 2009

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

Discrete & Computational Geometry, 2009

2008

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation.

SIAM Review, 2008

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

J. Comput. Syst. Sci., 2008

Simultaneous Communication Protocols with Quantum and Classical Messages.

Chicago J. Theor. Comput. Sci., 2008

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

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

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

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

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

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

Rounding Parallel Repetitions of Unique Games.

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.

Theory of Computing, 2007

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

SIAM J. Comput., 2007

The Unique Games Conjecture with Entangled Provers is False.

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

2006

The Complexity of the Local Hamiltonian Problem.

SIAM J. Comput., 2006

Combinatorial Algorithms for the Unsplittable Flow Problem.

Algorithmica, 2006

Lattice problems and norm embeddings.

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

Lattice-Based Cryptography.

Proceedings of the Advances in Cryptology, 2006

2005

A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover.

SIAM J. Comput., 2005

Lattice problems in NP cap coNP.

J. ACM, 2005

Conditional Hardness for Approximate Coloring

Electronic Colloquium on Computational Complexity (ECCC), 2005

The Hardness of 3-Uniform Hypergraph Coloring.

Combinatorica, 2005

The complexity of the covering radius problem.

Computational Complexity, 2005

2004

Improved Inapproximability of Lattice and Coding Problems With Preprocessing.

IEEE Trans. Information Theory, 2004

Quantum Computation and Lattice Problems.

SIAM J. Comput., 2004

New lattice-based cryptographic constructions.

J. ACM, 2004

Long Monotone Paths in Line Arrangements.

Discrete & Computational Geometry, 2004

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

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

2003

3-local Hamiltonian is QMA-complete.

Quantum Information & Computation, 2003

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

Inf. Process. Lett., 2003

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

Electronic Colloquium on Computational Complexity (ECCC), 2003

A Lattice Problem in Quantum NP.

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

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

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

2002

Off-line temporary tasks assignment.

Theor. Comput. Sci., 2002

Minimizing the Flow Time Without Migration.

SIAM J. Comput., 2002

Priority algorithms for makespan minimization in the subset model.

Inf. Process. Lett., 2002

Temporary tasks assignment resolved.

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

2001

On-line bin-stretching.

Theor. Comput. Sci., 2001

Strongly Polynomial Algorithms for the Unsplittable Flow Problem.

Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000

Maximizing job benefits on-line.

Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999

Off-Line Temporary Tasks Assignment.

Proceedings of the Algorithms, 1999

1998

Globally Distributed Computation over the Internet - The POPCORN Project.

Proceedings of the 18th International Conference on Distributed Computing Systems, 1998