Dorit Aharonov

Publication Activity (10 Years)

Years Active: 1996-2023
Publications (10 Years): 20

Top Topics

Information Theoretic

Error Reduction

Quantum Computing

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. STOC (2023)
Dorit Aharonov, Sandy Irani
Translationally Invariant Constraint Optimization Problems. CCC (2023)
Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, Or Sattath
The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings. Quantum 6 (2022)
Dorit Aharonov, Sandy Irani
Hamiltonian complexity in the thermodynamic limit. STOC (2022)
Dorit Aharonov, Sandy Irani
Translationally Invariant Constraint Optimization Problems. CoRR (2022)
Dorit Aharonov, Alex B. Grilo
Two Combinatorial MA-Complete Problems. ITCS (2021)
Dorit Aharonov, Michael Chapman
Technical perspective: On proofs, entanglement, and games. Commun. ACM 64 (11) (2021)
Dorit Aharonov, Alex B. Grilo, Yupan Liu
StoqMA vs. MA: the power of error reduction. CoRR (2020)
Dorit Aharonov, Alex B. Grilo
A combinatorial MA-complete problem. CoRR (2020)
Dorit Aharonov, Alex Bredariol Grilo
A combinatorial MA-complete problem. Electron. Colloquium Comput. Complex. 27 (2020)
Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, Or Sattath
On Quantum Advantage in Information Theoretic Single-Server PIR. CoRR (2019)
Dorit Aharonov, Alex Bredariol Grilo
Stoquastic PCP vs. Randomness. FOCS (2019)
Dorit Aharonov, Leo Zhou
Hamiltonian Sparsification and Gap-Simulation. ITCS (2019)
Dorit Aharonov, Alex Bredariol Grilo
Stoquastic PCP vs. Randomness. CoRR (2019)
Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, Or Sattath
On Quantum Advantage in Information Theoretic Single-Server PIR. EUROCRYPT (3) (2019)
Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, Or Sattath
On Quantum Advantage in Information Theoretic Single-Server PIR. IACR Cryptol. ePrint Arch. 2019 (2019)
Dorit Aharonov, Alex Bredariol Grilo
Stoquastic PCP vs. Randomness. Electron. Colloquium Comput. Complex. 26 (2019)
Dorit Aharonov, Oded Kenneth, Itamar Vigdorovich
On the Complexity of Two Dimensional Commuting Local Hamiltonians. TQC (2018)
Dorit Aharonov, Maor Ganz, Loïck Magnin
Dining Philosophers, Leader Election and Ring Size problems, in the quantum setting. CoRR (2017)
Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Loïck Magnin
A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias. SIAM J. Comput. 45 (3) (2016)
Dorit Aharonov, Lior Eldar
The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP. Quantum Inf. Process. 14 (1) (2015)
Dorit Aharonov, Lior Eldar
Quantum Locally Testable Codes. SIAM J. Comput. 44 (5) (2015)
Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. FOCS (2014)
Dorit Aharonov, Itai Arad, Thomas Vidick
Guest column: the quantum PCP conjecture. SIGACT News 44 (2) (2013)
Stefano Pironio, Dorit Aharonov
Quantum physics: A grip on misbehaviour. Nat. 496 (7446) (2013)
Dorit Aharonov, Itai Arad, Thomas Vidick
The Quantum PCP Conjecture. CoRR (2013)
Dorit Aharonov, Lior Eldar
Quantum Locally Testable Codes. CoRR (2013)
Dorit Aharonov, Lior Eldar
On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. FOCS (2011)
Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani
The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. FOCS (2011)
Dorit Aharonov, Michael Ben-Or, Elad Eban
Interactive Proofs For Quantum Computations. ICS (2010)
Dorit Aharonov, Vaughan Jones, Zeph Landau
A Polynomial Quantum Algorithm for Approximating the Jones Polynomial. Algorithmica 55 (3) (2009)
Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani
The detectability lemma and quantum gap amplification. STOC (2009)
Dorit Aharonov, Michael Ben-Or
Fault-Tolerant Quantum Computation with Constant Error Rate. SIAM J. Comput. 38 (4) (2008)
Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, Or Sattath
The Pursuit For Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings. CoRR (2008)
Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev
Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation. SIAM Rev. 50 (4) (2008)
Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe
The Power of Quantum Systems on a Line. FOCS (2007)
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) (2007)
Dorit Aharonov, Amnon Ta-Shma
Adiabatic Quantum State Generation. SIAM J. Comput. 37 (1) (2007)
Dorit Aharonov, Itai Arad
The BQP-hardness of approximating the Jones Polynomial. CoRR (2006)
Dorit Aharonov, Vaughan Jones, Zeph Landau
A polynomial quantum algorithm for approximating the Jones polynomial. STOC (2006)
Dorit Aharonov, Oded Regev
Lattice problems in NP cap coNP. J. ACM 52 (5) (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)
Dorit Aharonov, Oded Regev
Lattice Problems in NP cap coNP. FOCS (2004)
Dorit Aharonov, Oded Regev
A Lattice Problem in Quantum NP. FOCS (2003)
Dorit Aharonov, Amnon Ta-Shma
Adiabatic quantum state generation and statistical zero knowledge. STOC (2003)
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani
Quantum walks on graphs. STOC (2001)
Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao
Quantum bit escrow. STOC (2000)
Dorit Aharonov, Alexei Y. Kitaev, Noam Nisan
Quantum Circuits with Mixed States. STOC (1998)
Dorit Aharonov, Michael Ben-Or
Fault-Tolerant Quantum Computation With Constant Error. STOC (1997)
Dorit Aharonov, Michael Ben-Or
Polynomial Simulations of Decohered Quantum Computers. FOCS (1996)