Julia Kempe

Andris Ambainis, Julia Kempe, Or Sattath: A quantum lovász local lemma. J. ACM 59(5): 24 (2012)

Sevag Gharibian, Julia Kempe: Approximation Algorithms for QMA-Complete Problems. SIAM J. Comput. 41(4): 1028-1050 (2012)

Roy Kasher, Julia Kempe: Two-Source Extractors Secure Against Quantum Adversaries. Theory of Computing 8(1): 461-486 (2012)

Sevag Gharibian, Julia Kempe: Hardness of Approximation for Quantum Problems. ICALP (1) 2012: 387-398

Sevag Gharibian, Julia Kempe: Hardness of approximation for quantum problems. CoRR abs/1209.1055 (2012)

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick: Entangled Games Are Hard to Approximate. SIAM J. Comput. 40(3): 848-877 (2011)

Sevag Gharibian, Julia Kempe: Approximation Algorithms for QMA-Complete Problems. IEEE Conference on Computational Complexity 2011: 178-188

Julia Kempe, Thomas Vidick: Parallel repetition of entangled games. STOC 2011: 353-362

Sevag Gharibian, Julia Kempe: Approximation algorithms for QMA-complete problems. CoRR abs/1101.3884 (2011)

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper bounds on the noise threshold for fault-tolerant quantum computing. Quantum Information & Computation 10(5&6): 361-376 (2010)

Julia Kempe, Oded Regev, Ben Toner: Unique Games with Entangled Provers Are Easy. SIAM J. Comput. 39(7): 3207-3229 (2010)

Roy Kasher, Julia Kempe: Two-Source Extractors Secure against Quantum Adversaries. APPROX-RANDOM 2010: 656-669

Julia Kempe, Oded Regev: No Strong Parallel Repetition with Entangled and Non-signaling Provers. IEEE Conference on Computational Complexity 2010: 7-15

Andris Ambainis, Julia Kempe, Or Sattath: A quantum lovász local lemma. STOC 2010: 151-160

Roy Kasher, Julia Kempe: Two-Source Extractors Secure Against Quantum Adversaries. CoRR abs/1005.0512 (2010)

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick: Using Entanglement in Quantum Multi-Prover Interactive Proofs. Computational Complexity 18(2): 273-307 (2009)

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. SIAM J. Comput. 39(1): 1-24 (2009)

Julia Kempe, Oded Regev: No Strong Parallel Repetition with Entangled and Non-signaling Provers. CoRR abs/0911.0201 (2009)

Andris Ambainis, Julia Kempe, Or Sattath: A Quantum Lovasz Local Lemma. CoRR abs/0911.1696 (2009)

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM J. Comput. 38(5): 1695-1708 (2008)

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick: Using Entanglement in Quantum Multi-prover Interactive Proofs. IEEE Conference on Computational Complexity 2008: 211-222

Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick: Entangled Games are Hard to Approximate. FOCS 2008: 447-456

Julia Kempe, Oded Regev, Ben Toner: Unique Games with Entangled Provers are Easy. FOCS 2008: 457-466

Julia Kempe, Oded Regev, Falk Unger, Ronald de Wolf: Upper Bounds on the Noise Threshold for Fault-Tolerant Quantum Computing. ICALP (1) 2008: 845-856

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev: Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. SIAM J. Comput. 37(1): 166-194 (2007)

Julia Kempe, Oded Regev, Ben Toner: The Unique Games Conjecture with Entangled Provers is False. Algebraic Methods in Computational Complexity 2007

Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe: The Power of Quantum Systems on a Line. FOCS 2007: 373-383

Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf: Exponential separations for one-way quantum communication complexity, with applications to cryptography. STOC 2007: 516-525

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. SIAM J. Comput. 35(5): 1070-1097 (2006)

Jesse Fern, Julia Kempe, Slobodan N. Simic, Shankar Sastry: Generalized Performance of Concatenated Quantum Codes - A Dynamical Systems Approach. IEEE Trans. Automat. Contr. 51(3): 448-459 (2006)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Strengths and Weaknesses of Quantum Fingerprinting. IEEE Conference on Computational Complexity 2006: 288-298

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. STOC 2006: 594-603

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Strengths and Weaknesses of Quantum Fingerprinting. CoRR abs/quant-ph/0603173 (2006)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. CoRR abs/quant-ph/0607174 (2006)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Exponential Separation of Quantum and Classical One-Way Communication Complexity for a Boolean Function. Electronic Colloquium on Computational Complexity (ECCC) 13(086) (2006)

Andris Ambainis, Julia Kempe, Alexander Rivosh: Coins make quantum walks faster. SODA 2005: 1099-1108

Julia Kempe, Aner Shalev: The hidden subgroup problem and permutation group theory. SODA 2005: 1118-1125

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-Error Quantum State Identification and Exponential Separations in Communication Complexity. CoRR abs/quant-ph/0511013 (2005)

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev: Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. FOCS 2004: 42-51

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. FSTTCS 2004: 372-383

Julia Kempe, Aner Shalev: The hidden subgroup problem and permutation group theory. CoRR quant-ph/0406046 (2004)

Julia Kempe, Alexei Kitaev, Oded Regev: The Complexity of the Local Hamiltonian Problem. CoRR quant-ph/0406180 (2004)

Dmitry Gavinsky, Julia Kempe, Ronald de Wolf: Quantum Communication Cannot Simulate a Public Coin. CoRR quant-ph/0411051 (2004)

Julia Kempe, Oded Regev: 3-local Hamitonian is QMA-complete. Quantum Information & Computation 3(3): 258-264 (2003)

Julia Kempe: Discrete Quantum Walks Hit Exponentially Faster. RANDOM-APPROX 2003: 354-369

Julia Kempe: Quantum Random Walks Hit Exponentially Faster. CoRR quant-ph/0205083 (2002)

Julia Kempe, David Bacon, David P. DiVincenzo, K. Brigitta Whaley: Encoded universality from a single physical interaction. Quantum Information & Computation 1(4): 33-55 (2001)

Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani: Quantum walks on graphs. STOC 2001: 50-59