John Watrous

Publication Activity (10 Years)

Years Active: 1995-2023
Publications (10 Years): 14

Top Topics

Nash Equilibria

Quantum Computation

Top Venues

Chic. J. Theor. Comput. Sci.

IEEE Trans. Inf. Theory

Publications

Soumik Ghosh, John Watrous
Complexity Limitations on One-turn Quantum Refereed Games. Theory Comput. Syst. 67 (2) (2023)
John Bostanci, John Watrous
Quantum game theory and the complexity of approximating quantum Nash equilibria. Quantum 6 (2022)
John Bostanci, John Watrous
Quantum game theory and the complexity of approximating quantum Nash equilibria. CoRR (2021)
Bryan Coutts, Mark Girard, John Watrous
Certifying optimality for convex quantum channel optimization problems. Quantum 5 (2021)
Soumik Ghosh, John Watrous
Complexity limitations on one-turn quantum refereed games. CoRR (2020)
Colin Do-Yan Lee, John Watrous
Detecting mixed-unitary quantum channels is NP-hard. Quantum 4 (2020)
Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous
Zero-Knowledge Proof Systems for QMA. SIAM J. Comput. 49 (2) (2020)
Colin Do-Yan Lee, John Watrous
Detecting mixed-unitary quantum channels is NP-hard. CoRR (2019)
Vincent Russo, John Watrous
Extended Nonlocal Games from Quantum-Classical Games. Chic. J. Theor. Comput. Sci. 2018 (2018)
Sanketh Menda, John Watrous
Oracle Separations for Quantum Statistical Zero-Knowledge. CoRR (2018)
Abel Molina, John Watrous
Revisiting the simulation of quantum Turing machines by quantum circuits. CoRR (2018)
Thomas Vidick, John Watrous
Quantum Proofs. Found. Trends Theor. Comput. Sci. 11 (1-2) (2016)
Anne Broadbent, Zheng-Feng Ji, Fang Song, John Watrous
Zero-knowledge proof systems for QMA. CoRR (2016)
Anne Broadbent, Zhengfeng Ji, Fang Song, John Watrous
Zero-Knowledge Proof Systems for QMA. FOCS (2016)
Somshubhro Bandyopadhyay, Alessandro Cosentino, Nathaniel Johnston, Vincent Russo, John Watrous, Nengkun Yu
Limitations on Separable Measurements by Convex Optimization. IEEE Trans. Inf. Theory 61 (6) (2015)
John Watrous
Simpler semidefinite programs for completely bounded norms. Chic. J. Theor. Comput. Sci. 2013 (2013)
Debbie W. Leung, Benjamin Toner, John Watrous
Coherent state exchange in multi-prover quantum interactive proof systems. Chic. J. Theor. Comput. Sci. 2013 (2013)
Tsuyoshi Ito, Hirotada Kobayashi, John Watrous
Quantum interactive proofs with weak error bounds. ITCS (2012)
Kousha Etessami, Dieter van Melkebeek, Seth Pettie, John Watrous, Salil P. Vadhan
Special Section on the Forty-Third Annual ACM Symposium on Theory of Computing (STOC 2011). SIAM J. Comput. 41 (5) (2012)
Abel Molina, Thomas Vidick, John Watrous
Optimal Counterfeiting Attacks and Generalizations for Wiesner's Quantum Money. TQC (2012)
John Watrous
Guest column: an introduction to quantum information and quantum circuits 1. SIGACT News 42 (2) (2011)
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
QIP = PSPACE. J. ACM 58 (6) (2011)
Salman Beigi, Peter W. Shor, John Watrous
Quantum Interactive Proofs with Short Messages. Theory Comput. 7 (1) (2011)
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
QIP = PSPACE. STOC (2010)
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous
QIP = PSPACE. Commun. ACM 53 (12) (2010)
Tsuyoshi Ito, Hirotada Kobayashi, John Watrous
Quantum interactive proofs with weak error bounds CoRR (2010)
Salman Beigi, Peter W. Shor, John Watrous
Quantum interactive proofs with short messages CoRR (2010)
John Watrous
Mixing doubly stochastic quantum channels with the completely depolarizing channel. Quantum Inf. Comput. 9 (5&6) (2009)
Rahul Jain, John Watrous
Parallel Approximation of Non-interactive Zero-sum Quantum Games. Computational Complexity Conference (2009)
John Watrous
Zero-Knowledge against Quantum Attacks. SIAM J. Comput. 39 (1) (2009)
Rahul Jain, Sarvagya Upadhyay, John Watrous
Two-message quantum interactive proofs are in PSPACE CoRR (2009)
John Watrous
Semidefinite Programs for Completely Bounded Norms. Theory Comput. 5 (1) (2009)
Rahul Jain, Sarvagya Upadhyay, John Watrous
Two-Message Quantum Interactive Proofs Are in PSPACE. FOCS (2009)
Scott Aaronson, John Watrous
Closed Timelike Curves Make Quantum and Classical Computing Equivalent. CoRR (2008)
John Watrous
Distinguishing quantum operations having few Kraus operators. Quantum Inf. Comput. 8 (8) (2008)
Scott Aaronson, John Watrous
Closed Timelike Curves Make Quantum and Classical Computing Equivalent. Electron. Colloquium Comput. Complex. 15 (092) (2008)
Gus Gutoski, John Watrous
Toward a general theory of quantum games. STOC (2007)
John Watrous
Zero-knowledge against quantum attacks. STOC (2006)
Gus Gutoski, John Watrous
Toward a general theory of quantum games CoRR (2006)
Gus Gutoski, John Watrous
Quantum Interactive Proofs with Competing Provers. STACS (2005)
John Watrous
Notes on super-operator norms induced by schatten norms. Quantum Inf. Comput. 5 (1) (2005)
Chris Marriott, John Watrous
Quantum Arthur-Merlin games. Comput. Complex. 14 (2) (2005)
Chris Marriott, John Watrous
Quantum Arthur-Merlin Games CoRR (2005)
Bill Rosgen, John Watrous
On the hardness of distinguishing mixed-state quantum computations CoRR (2004)
Eric Bach, Susan N. Coppersmith, Marcel Paz Goldschen, Robert Joynt, John Watrous
One-dimensional quantum walks with absorbing boundaries. J. Comput. Syst. Sci. 69 (4) (2004)
Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous
Consequences and Limits of Nonlocal Strategies. Computational Complexity Conference (2004)
Chris Marriott, John Watrous
Quantum Arthur-Merlin Games. Computational Complexity Conference (2004)
Gus Gutoski, John Watrous
Quantum Interactive Proofs with Competing Provers CoRR (2004)
Heath Gerhardt, John Watrous
Continuous-Time Quantum Walks on the Symmetric Group. RANDOM-APPROX (2003)
John Watrous
On the complexity of simulating space-bounded quantum computations. Comput. Complex. 12 (1-2) (2003)
John Watrous
PSPACE has constant-round quantum interactive proof systems. Theor. Comput. Sci. 292 (3) (2003)
John Watrous
Arthur and Merlin in a Quantum World. Computational Complexity Conference (2002)
J. Niel de Beaudrap, Richard Cleve, John Watrous
Sharp Quantum versus Classical Query Complexity Separations. Algorithmica 34 (4) (2002)
John Watrous
imits on the Power of Quantum Statistical Zero-Knowledge. FOCS (2002)
Andris Ambainis, John Watrous
Two-way finite automata with quantum and classical state. Theor. Comput. Sci. 287 (1) (2002)
John Watrous
Quantum algorithms for solvable groups. STOC (2001)
Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
One-dimensional quantum walks. STOC (2001)
John Watrous
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. J. Comput. Syst. Sci. 62 (2) (2001)
John Watrous
Succinct quantum proofs for properties of finite groups. FOCS (2000)
Richard Cleve, John Watrous
Fast parallel circuits for the quantum Fourier transform. FOCS (2000)
John Watrous
Succinct quantum proofs for properties of finite groups CoRR (2000)
Alexei Y. Kitaev, John Watrous
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. STOC (2000)
John Watrous
Quantum Simulations of Classical Random Walks and Undirected Graph Connectivity. Computational Complexity Conference (1999)
John Watrous
PSPACE Has Constant-Round Quantum Interactive Proof Systems. FOCS (1999)
John Watrous
On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. FOCS (1999)
Andris Ambainis, John Watrous
Two-way finite automata with quantum and classical states CoRR (1999)
John Watrous
On quantum and classical space-bounded processes with algebraic transition amplitudes CoRR (1999)
John Watrous
Space-Bounded Quantum Complexity. J. Comput. Syst. Sci. 59 (2) (1999)
John Watrous
PSPACE has 2-round quantum interactive proof systems CoRR (1999)
John Watrous
Quantum simulations of classical random walks and undirected graph connectivity CoRR (1998)
John Watrous
Relationships Between Quantum and Classical Space-Bounded Complexity Classes. Computational Complexity Conference (1998)
Attila Kondacs, John Watrous
On the Power of Quantum Finite State Automata. FOCS (1997)
John Watrous
On One-Dimensional Quantum Cellular Automata. FOCS (1995)