BQP and PPAD

Theory and applications of trapdoor functions (extended abstract)

Andrew Chi-Chih Yao · 1982

Earlier work this paper cites.

How to generate cryptographically strong sequences of pseudo-random bits

Manuel Blum and Silvio Micali · 1984

Earlier work this paper cites.

A hard-core predicate for all one-way functions

Oded Goldreich and Leonid A. Levin · 1989

Earlier work this paper cites.

On total functions, existence theorems, and computational complexity

Nimrod Megiddo and Christos Papadimitriou · 1991

Earlier work this paper cites.

Pseudorandom bits for constant depth circuits

Noam Nisan · 1991

Earlier work this paper cites.

Pseudorandom generators for space-bounded computation

Noam Nisan · 1992

Earlier work this paper cites.

Pseudorandomness for network algorithms

Russell Impagliazzo, Noam Nisan, and Avi Wigderson · 1994

Earlier work this paper cites.

Hardness vs randomness

Noam Nisan and Avi Wigderson · 1994

Cited alongside, same era.

On the complexity of the parity argument and other inefficient proofs of existence

Christos Papadimitriou · 1994

Cited alongside, same era.

Strengths and weaknesses of quantum computing

Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997

Cited alongside, same era.

Quantum complexity theory

Ethan Bernstein and Umesh Vazirani · 1997

Cited alongside, same era.

Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer

Peter Shor · 1997

Cited alongside, same era.

A pseudorandom generator from any one-way function

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby · 1999

Cited alongside, same era.

Algorithms, games, and the internet

Christos H. Papadimitriou · 2001

Later among the works it cites.

Lecture Notes of Quantum Computing

Umesh Vazirani, 2004 · 2004

Later among the works it cites.

Algorithmic Game Theory

Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay Vazirani · 2007

Later among the works it cites.

Settling the complexity of computing two-player Nash equilibria

Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009

Later among the works it cites.

The complexity of computing a Nash equilibrium

Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou · 2009

Later among the works it cites.

BQP and the polynomial hierarchy

Scott Aaronson · 2010

Later among the works it cites.