Dorit Aharonov

According to our database, Dorit Aharonov authored at least 39 papers between 1996 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2023

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling.

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Translationally Invariant Constraint Optimization Problems.

Dorit Aharonov, Sandy Irani

Proceedings of the 38th Computational Complexity Conference, 2023

2022

The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings.

Dorit Aharonov, Michael Ben-Or, Fernando G. S. L. Brandão, Or Sattath

Quantum, 2022

Hamiltonian complexity in the thermodynamic limit.

Dorit Aharonov, Sandy Irani

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Technical perspective: On proofs, entanglement, and games.

Dorit Aharonov, Michael Chapman

Commun. ACM, 2021

Two Combinatorial MA-Complete Problems.

Dorit Aharonov, Alex B. Grilo

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

A combinatorial MA-complete problem.

Dorit Aharonov, Alex Bredariol Grilo

Electron. Colloquium Comput. Complex., 2020

StoqMA vs. MA: the power of error reduction.

Dorit Aharonov, Alex B. Grilo, Yupan Liu

CoRR, 2020

2019

On Quantum Advantage in Information Theoretic Single-Server PIR.

Dorit Aharonov, Zvika Brakerski, Kai-Min Chung, Ayal Green, Ching-Yi Lai, Or Sattath

IACR Cryptol. ePrint Arch., 2019

Stoquastic PCP vs. Randomness.

Dorit Aharonov, Alex Bredariol Grilo

Electron. Colloquium Comput. Complex., 2019

Hamiltonian Sparsification and Gap-Simulation.

Dorit Aharonov, Leo Zhou

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

On the Complexity of Two Dimensional Commuting Local Hamiltonians.

Dorit Aharonov, Oded Kenneth, Itamar Vigdorovich

Proceedings of the 13th Conference on the Theory of Quantum Computation, 2018

2017

Dining Philosophers, Leader Election and Ring Size problems, in the quantum setting.

Dorit Aharonov, Maor Ganz, Loïck Magnin

CoRR, 2017

2016

A Simpler Proof of the Existence of Quantum Weak Coin Flipping with Arbitrarily Small Bias.

Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Loïck Magnin

SIAM J. Comput., 2016

2015

Quantum Locally Testable Codes.

Dorit Aharonov, Lior Eldar

SIAM J. Comput., 2015

The commuting local Hamiltonian problem on locally expanding graphs is approximable in NP.

Dorit Aharonov, Lior Eldar

Quantum Inf. Process., 2015

2014

Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law.

Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Guest column: the quantum PCP conjecture.

Dorit Aharonov, Itai Arad, Thomas Vidick

SIGACT News, 2013

Quantum physics: A grip on misbehaviour.

Stefano Pironio, Dorit Aharonov

Nat., 2013

The Quantum PCP Conjecture.

Dorit Aharonov, Itai Arad, Thomas Vidick

CoRR, 2013

2011

On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems.

Dorit Aharonov, Lior Eldar

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach.

Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

Interactive Proofs For Quantum Computations.

Dorit Aharonov, Michael Ben-Or, Elad Eban

Proceedings of the Innovations in Computer Science, 2010

2009

A Polynomial Quantum Algorithm for Approximating the Jones Polynomial.

Dorit Aharonov, Vaughan Jones, Zeph Landau

Algorithmica, 2009

The detectability lemma and quantum gap amplification.

Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Adiabatic Quantum Computation Is Equivalent to Standard Quantum Computation.

Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev

SIAM Rev., 2008

Fault-Tolerant Quantum Computation with Constant Error Rate.

Dorit Aharonov, Michael Ben-Or

SIAM J. Comput., 2008

2007

Adiabatic Quantum State Generation.

Dorit Aharonov, Amnon Ta-Shma

SIAM J. Comput., 2007

The Power of Quantum Systems on a Line.

Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

The BQP-hardness of approximating the Jones Polynomial.

Dorit Aharonov, Itai Arad

CoRR, 2006

2005

Lattice problems in NP cap coNP.

Dorit Aharonov, Oded Regev

J. ACM, 2005

2003

Adiabatic quantum state generation and statistical zero knowledge.

Dorit Aharonov, Amnon Ta-Shma

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

A Lattice Problem in Quantum NP.

Dorit Aharonov, Oded Regev

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

2001

Quantum walks on graphs.

Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000

Quantum bit escrow.

Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

1999

Noisy quantum computation (חשוב קוונטי רועש.).

Dorit Aharonov

PhD thesis, 1999

1998

Quantum Circuits with Mixed States.

Dorit Aharonov, Alexei Y. Kitaev, Noam Nisan

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Fault-Tolerant Quantum Computation With Constant Error.

Dorit Aharonov, Michael Ben-Or

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Polynomial Simulations of Decohered Quantum Computers.

Dorit Aharonov, Michael Ben-Or

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996