@article{Regev12,
author = {Regev, Oded},
title = {Entropy-based Bounds on Dimension Reduction in $L_1$},
journal = {Israel Journal of Mathematics},
volume_ = {},
number_ = {},
year = {2012},
pages_ = {},
note = {arXiv:1108.1283},
}
@article{Regev11,
author = {Regev, Oded},
title = {Bell Violations through Independent Bases Games},
journal = {Quantum Information and Computation},
volume = {12},
number = {1},
year = {2012},
pages = {9--20},
note = {arXiv:1101.0576},
}
@InProceedings{BuhrmanRSW11,
AUTHOR = "H. Buhrman and O. Regev and G. Scarpa and {de Wolf}, R.",
title = {Near-Optimal and Explicit {B}ell Inequality Violations},
booktitle = "Proc. of 26th IEEE Annual Conference on Computational Complexity (CCC)",
year = {2011},
pages = {157--166},
NOTE = "arXiv:1012.5043",
}
@InProceedings{ChakrabartiR10,
author = {Chakrabarti, Amit and Regev, Oded},
title = {An Optimal Lower Bound on the Communication Complexity of Gap {H}amming Distance},
booktitle = "Proc. 43rd Annual ACM Symposium on the Theory of Computing",
year = {2011},
pages = {51--60},
}
@InProceedings{KlartagR10,
author = {Klartag, Bo'az and Regev, Oded},
title = {Quantum One-Way Communication can be Exponentially Stronger Than Classical Communication},
booktitle = "Proc. 43rd Annual ACM Symposium on the Theory of Computing",
year = {2011},
pages = {31--40},
}
@inproceedings{KempeR10,
author = {Kempe, Julia and Regev, Oded},
title = {No Strong Parallel Repetition with Entangled and Non-signaling Provers},
booktitle = {Proc. of 25th IEEE Annual Conference on Computational Complexity (CCC)},
year = {2010},
pages = {7--15},
}
@inproceedings{Regev10,
author = {Regev, Oded},
title = {The Learning with Errors Problem},
booktitle = {Proc. of 25th IEEE Annual Conference on Computational Complexity (CCC)},
year = {2010},
pages_ = {},
}
@InProceedings{RegevS08,
Author = {O. Regev and L. Schiff},
Title = {Impossibility of a {G}rover speed-up with a faulty oracle},
BookTitle = {35th International Colloquium on Automata, Languages and Programming (ICALP)},
year = 2008,
pages = {773--781},
}
@InProceedings{EldarR08,
Author = {L. Eldar and O. Regev},
Title = {Quantum SAT for a qutrit-cinquit pair is QMA1-complete},
BookTitle = {35th International Colloquium on Automata, Languages and Programming (ICALP)},
year = 2008,
pages = {881--892},
}
@article{KempeRUdW10,
author = {Kempe, Julia and Regev, Oded and Unger, Falk and de Wolf, Ronald},
title = {Upper Bounds on the Noise Threshold for Fault-tolerant Quantum Computing},
journal = {Quantum Information and Computation},
volume = {10},
number = {5},
year = {2010},
pages = {361--376},
note = {Preliminary version in ICALP'08},
conf_year = 2008,
}
journal = {Quantum Information and Computation},
volume = {10},
number = {5},
year = {2010},
pages = {361--376},
note = {Preliminary version in ICALP'08},
proc_year = 2008,
}
@article{KempeRT08,
author = {Kempe, Julia and Regev, Oded and Toner, Ben},
title = {Unique Games with Entangled Provers are Easy},
publisher = {SIAM},
year = {2010},
journal = {SIAM Journal on Computing},
volume = {39},
number = {7},
pages = {3207-3229},
keywords = {two-prover one-round games; quantum entanglement; semidefinite programming; parallel repetition},
url = {http://link.aip.org/link/?SMJ/39/3207/1},
doi = {10.1137/090772885},
proc_booktitle = {Proc. 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2008},
proc_pages = {457--466},
note = {Preliminary version in FOCS'08},
}
@article{RegevT09,
author = {Regev, Oded and Toner, Ben},
title = {Simulating Quantum Correlations with Finite Communication},
journal = {SIAM Journal on Computing},
volume = {39},
number = {4},
pages = {1562--1580},
year = {2009},
doi = {10.1137/080723909},
note = {Preliminary version in FOCS'07},
proc_booktitle = {Proc. 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2007},
proc_pages = {384--394},
}
@inproceedings{BarakHHRRS08,
author = {Boaz Barak and Moritz Hardt and Ishay Haviv and Anup Rao and Oded Regev and David Steurer},
title = {Rounding Parallel Repetitions of Unique Games},
booktitle = {Proc. 49th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
year = {2008},
pages = {374--383},
}
@article{HavivLR09,
author = {Haviv, Ishay and Lyubashevsky, Vadim and Regev, Oded},
title = {A Note on the Distribution of the Distance from a Lattice},
journal = {Discrete and Computational Geometry},
volume = {41},
number = {1},
year = {2009},
pages = {162--176},
}
@article{GavinskyKRW06,
author = {Gavinsky, Dmitry and Kempe, Julia and Regev, Oded and de Wolf, Ronald},
title = {Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity},
journal = {SIAM Journal on Computing},
volume = {39},
number = {1},
pages = {1--24},
year = {2009},
doi = {10.1137/060665798},
note = {Preliminary version in STOC'06},
proc_booktitle = {Proc. 38th ACM Symp. on Theory of Computing (STOC)},
proc_year = {2006},
proc_pages = {594--603},
}
@article{GavinskyRW08,
author={Dmitry Gavinsky and Oded Regev and Ronald de Wolf},
title={Simultaneous Communication Protocols with Quantum and Classical Messages},
journal={Chicago Journal of Theoretical Computer Science},
volume={2008},
number={7},
publisher={University of Chicago},
month={December},
year={2008},
URL = {http://cjtcs.cs.uchicago.edu/articles/2008/7/contents.html}
}
@InCollection{MicciancioR08,
author = "Micciancio, Daniele and Regev, Oded",
title = "Lattice-based Cryptography",
chapter = "",
year = "2008",
editor = "D. J. Bernstein and J. Buchmann",
publisher = "Springer",
booktitle = "Post-quantum Cryptography",
}
@article{HavivRT07,
author = {Ishay Haviv and Oded Regev and Amnon Ta-Shma},
title = {On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy},
journal = {Theory of Computing},
year = {2007},
volume = {3},
number = {3},
pages = {45--60},
publisher = {Theory of Computing},
eprint = {toc:v003/a003},
URL = {http://www.theoryofcomputing.org/articles/main/v003/a003},
}
@inproceedings{HavivR07,
author = {Haviv, Ishay and Regev, Oded},
title = {Tensor-based Hardness of the Shortest Vector Problem to within Almost Polynomial Factors},
booktitle = {Proc. 39th ACM Symp. on Theory of Computing (STOC)},
year = {2007},
pages = {469--477},
}
@article{MosselORSS06,
author = {Mossel, Elchanan and O'Donnell, Ryan and Regev, Oded and Steif, Jeffrey E. and Sudakov, Benny},
title = {Non-interactive correlation distillation, inhomogeneous {M}arkov
chains, and the reverse {B}onami-{B}eckner inequality},
journal = {Israel Journal of Mathematics},
volume = {154},
number__ = {},
pages = {299--336},
year = {2006},
}
@inproceedings{R06,
author = {Regev, Oded},
title = {Lattice-based Cryptography},
booktitle = {Advances in cryptology ({CRYPTO})},
year = {2006},
pages = {131--141},
}
@article{NguyenR06,
author = {Nguyen, Phong Q. and Regev, Oded},
title = {Learning a Parallelepiped: Cryptanalysis of {GGH} and {NTRU} Signatures},
journal = {Journal of Cryptology},
volume = 22,
number = 2,
year = 2009,
pages = {139--160},
proc_booktitle = {The 25th International Cryptology Conference (Eurocrypt)},
proc_year = {2006},
proc_pages = {271--288},
note = {Preliminary version in Eurocrypt 2006},
}
@article{DinurFR06,
author = {Dinur, Irit and Friedgut, Ehud and Regev, Oded},
title = {Independent Sets in Graph Powers are Almost Contained in Juntas},
journal = {GAFA},
volume = 18,
number = 1,
year = {2008},
pages = {77--97},
}
@inproceedings{HavivR06,
author = {Haviv, Ishay and Regev, Oded},
title = {Hardness of the Covering Radius Problem on Lattices},
booktitle = {Proc. of 21st IEEE Annual Conference on Computational Complexity (CCC)},
year = {2006},
pages = {145--158},
}
@inproceedings{RegevR06,
author = {Regev, Oded and Rosen, Ricky},
title = {Lattice Problems and Norm Embeddings},
booktitle = {Proc. 38th ACM Symp. on Theory of Computing (STOC)},
year = {2006},
pages = {447--456},
}
@article{DinurMR06,
author = {Dinur, Irit and Mossel, Elchanan and Regev, Oded},
title = {Conditional Hardness for Approximate Coloring},
journal = {SIAM Journal on Computing},
volume = {39},
number = {3},
pages = {843--873},
year = {2009},
note = {Preliminary version in STOC'06},
proc_booktitle = {Proc. 38th ACM Symp. on Theory of Computing (STOC)},
proc_year = {2006},
proc_pages = {344--353},
}
@article{Regev05,
author = {Regev, Oded},
title = {On lattices, learning with errors, random linear codes, and cryptography},
note = {Preliminary version in STOC'05},
journal = {Journal of the ACM},
volume = {56},
number = {6},
pages = {34},
year = {2009},
proc_booktitle = {Proc. 37th ACM Symp. on Theory of Computing (STOC)},
proc_year = {2005},
proc_pages = {84--93},
}
@misc{AmbainisR04,
author = {Ambainis, Andris and Regev, Oded},
title = {An Elementary Proof of the Adiabatic Theorem},
note= {quant-ph/0411152},
year = {2004},
}
@article{KempeKR04,
author = {Kempe, Julia and Kitaev, Alexei and Regev, Oded},
title = {The Complexity of the {L}ocal {H}amiltonian {P}roblem},
journal = {SIAM Journal on Computing},
volume = {35},
number = {5},
pages = {1070--1097},
year = {2006},
note = {Preliminary version in FSTTCS'04},
proc_booktitle = {Proc. of FSTTCS},
proc_year = {2004},
proc_pages = {595--601},
}
@misc{Regev04A,
author = {Regev, Oded},
title = {A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space},
note= {{\tt quant-ph/0406151}},
year = {2004},
}
@article{AharonovDKLLR04,
author = {Aharonov, Dorit and van Dam, Wim and Kempe, Julia and Landau, Zeph and Lloyd, Seth and Regev, Oded},
title = {Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation},
publisher = {SIAM},
year = {2007},
journal = {SIAM Journal on Computing},
volume = {37},
number = {1},
pages = {166--194},
keywords = {quantum computation; adiabatic computation; nearest neighbor interactions},
url = {http://link.aip.org/link/?SMJ/37/166/1},
doi = {10.1137/S0097539705447323},
proc_booktitle = {Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2004},
proc_pages = {42--51},
}
@article{MicciancioR04,
author = {Micciancio, Daniele and Regev, Oded},
title = {Worst-case to Average-case Reductions Based on {G}aussian Measures},
publisher = {SIAM},
year = {2007},
journal = {SIAM Journal on Computing},
volume = {37},
number = {1},
pages = {267--302},
keywords = {lattices; worst-case to average-case reductions; Gaussian measures},
url = {http://link.aip.org/link/?SMJ/37/267/1},
doi = {10.1137/S0097539705447360},
proc_booktitle = {Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2004},
proc_pages = {372--381},
}
@article{ChakrabartiR04,
author = {Chakrabarti, Amit and Regev, Oded},
title = {An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching},
journal = {SIAM Journal on Computing},
volume = {39},
number = {5},
pages = {1919--1940},
note = {Preliminary version in FOCS'04},
year = {2010},
proc_booktitle = {Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2004},
proc_pages = {473--482},
}
@article{AharonovR04,
author = {Aharonov, Dorit and Regev, Oded},
title = {Lattice Problems in {NP} intersect {coNP}},
note = {Preliminary version in FOCS'04},
journal = {Journal of the ACM},
volume = {52},
number = {5},
pages = {749--765},
year = {2005},
proc_booktitle = {Proc. 45th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2004},
proc_pages = {362--371},
}
@article{GuruswamiMR04,
author = {Guruswami, Venkatesan and Micciancio, Daniele and Regev, Oded},
title = {The Complexity of the Covering Radius Problem on Lattices and Codes},
journal = {Computational Complexity},
volume = {14},
number = {2},
year = {2005},
pages = {90--121},
note = {Preliminary version in CCC'04},
proc_booktitle = {Proc. of 19th IEEE Annual Conference on Computational Complexity (CCC)},
proc_year = {2004},
proc_pages = {161--173},
}
@inproceedings{AharonovR03,
author = {Aharonov, Dorit and Regev, Oded},
title = {A Lattice Problem in Quantum {NP}},
booktitle = {Proc. 44th Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
year = {2003},
pages = {210--219},
}
@article{KhotR03,
author = {Khot, Subhash and Regev, Oded},
title = {Vertex Cover Might be Hard to Approximate to within $2-\varepsilon$},
journal = {Journal of Computer and System Sciences (JCSS)},
volume = {74},
number = {3},
pages = {335--349},
year = {2008},
note = {Preliminary version in CCC'03},
proc_booktitle = {Proc. of 18th IEEE Annual Conference on Computational Complexity (CCC)},
proc_year = {2003},
proc_pages = {379--386},
}
@article{Regev03B,
author = {Regev, Oded},
title = {Improved inapproximability of lattice and coding problems with preprocessing},
journal = {IEEE Transactions on Information Theory},
volume = {50},
number = {9},
year = {2004},
pages = {2031--2037},
note = {Preliminary version in CCC'03},
proc_booktitle = {Proc. of 18th IEEE Annual Conference on Computational Complexity (CCC)},
proc_year = {2003},
proc_pages = {363--370},
}
@article{KempeR03,
author = {Kempe, Julia and Regev, Oded},
title = {3-Local {H}amiltonian is {QMA}-complete},
journal = {Quantum Information and Computation},
volume = {3},
number = {3},
year = {2003},
pages = {258--264},
}
@article{BaloghRSSS03,
author = {Balogh, Jozsef and Regev, Oded and Smyth, Clifford and Steiger, William and Szegedy, Mario},
title = {Long monotone paths in line arrangements},
journal = {Discrete and Computational Geometry},
volume = {32},
number = {2},
year = {2004},
pages = {167--176},
note = {Preliminary version in SOCG'03},
proc_booktitle = {Proc. 19th ACM Symp. on Computational Geometry (SOCG)},
proc_year = {2003},
proc_pages = {124--128},
}
@article{DinurGKR03,
author = {Dinur, Irit and Guruswami, Venkatesan and Khot, Subhash and Regev, Oded},
title = {A new multilayered {PCP} and the hardness of hypergraph vertex cover},
journal = {SIAM Journal on Computing},
volume = {34},
number = {5},
pages = {1129--1146},
year = {2005},
note = {Preliminary version in STOC'03},
proc_booktitle = {Proc. 35th ACM Symp. on Theory of Computing (STOC)},
proc_year = {2003},
proc_pages = {595--601},
}
@article{Regev03A,
author = {Regev, Oded},
title = {New lattice-based cryptographic constructions},
note = {Preliminary version in STOC'03},
journal = {Journal of the ACM},
volume = {51},
number = {6},
pages = {899--942},
year = {2004},
proc_booktitle = {Proc. 35th ACM Symp. on Theory of Computing (STOC)},
proc_year = {2003},
proc_pages = {407--416},
}
@article{DinurRS02,
author = {Dinur, Irit and Regev, Oded and Smyth, Clifford},
title = {The hardness of 3-uniform hypergraph coloring},
note = {Preliminary version in FOCS'02},
journal = {Combinatorica},
volume = {25},
number = {5},
pages = {519--535},
year = {2005},
proc_booktitle = {Proc. 43rd Annual IEEE Symp. on Foundations of Computer Science (FOCS)},
proc_year = {2002},
proc_pages = {33--40},
}
@article {Regev02B,
AUTHOR = {Regev, Oded},
TITLE = {Quantum computation and lattice problems},
JOURNAL = {SIAM Journal on Computing},
VOLUME = {33},
YEAR = {2004},
NUMBER = {3},
PAGES = {738--760},
NOTE = {Preliminary version in FOCS'02}
}
@article{Regev02A,
author = {Regev, Oded},
title = {Priority algorithms for makespan minimization in the subset model},
journal = {Information Processing Letters},
volume = {84},
number = {3},
year = {2003},
pages = {153--157},
}
@article{ArmonAER03B,
author = {Armon, Amitai and Azar, Yossi and Epstein, Leah and Regev, Oded},
title = {On-line restricted assignment of temporary tasks with unknown durations},
journal = {Information Processing Letters},
volume = {85},
number = {2},
year = {2003},
pages = {67--72},
}
@article{ArmonAER03A,
author = {Armon, Amitai and Azar, Yossi and Epstein, Leah and Regev, Oded},
title = {Temporary tasks assignment resolved},
journal = {Algorithmica},
volume = {36},
number = {3},
year = {2003},
pages = {295--314},
note = {Preliminary version in {\em Proc. of SODA}, 2002},
}
@article{AzarR01B,
author = {Azar, Yossi and Regev, Oded},
title = {Combinatorial Algorithms for the Unsplittable Flow Problem},
journal = {Algorithmica},
volume = {44},
number = {1},
year = {2006},
pages = {49--66},
note = {Preliminary version in {\em Proc. of IPCO}, 2001},
proc_booktitle = {Proc. 8th Conf. on Integer Programming and Combinatorial Optimization (IPCO)},
proc_pages = {15--29},
proc_year = {2001},
}
@article{AwerbuchAR01,
author = {Awerbuch, Baruch and Azar, Yossi and Regev, Oded},
title = {Maximizing job benefits on-line},
journal = {Journal of Scheduling},
volume = {4},
number = {6},
year = {2001},
pages = {287--296},
note = {Preliminary version in {\em Proc. of APPROX}, 2000},
}
@article{AwerbuchALR02,
author = {Awerbuch, Baruch and Azar, Yossi and Leonardi, Stefano and Regev, Oded},
title = {Minimizing the flow time without migration},
journal = {SIAM Journal on Computing},
volume = {31},
number = {5},
year = {2002},
pages = {1370--1382},
note = {Preliminary version in {\em Proc. of STOC}, 1999},
}
@article{AzarRSW02,
author = {Azar, Yossi and Regev, Oded and Sgall, Ji{\v r}{\'\i} and Woeginger, Gerhard},
title = {Off-line temporary tasks assignment},
journal ={Theoretical Computer Science},
volume = {287},
number = {2},
year = {2002},
pages = {419--428},
note = {Preliminary version in {\em Proc. of ESA}, 1999},
}
@article{AzarR01A,
author = {Azar, Yossi and Regev, Oded},
title = {On-line bin stretching},
journal = {Theoretical Computer Science},
volume = {268},
number = {1},
year = {2001},
pages = {17--41},
note = {Preliminary version in {\em Proc. of RANDOM}, 1998},
}