@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},
}