Andrew Chi-Chih Yao

Would physical laws permit the construction of computing machines

that are capable of solving some problems much faster than the

standard computational model? Recent evidence suggests that this

might be the case in the quantum world. But the question is of

great interest even in the realm of classical physics. ...
more >>>

Scott Aaronson

In a sampling problem, we are given an input $x\in\left\{0,1\right\} ^{n}$, and asked to sample approximately from a probability

distribution $D_{x}$ over poly(n)-bit strings. In a search problem, we are given an input

$x\in\left\{ 0,1\right\} ^{n}$, and asked to find a member of a nonempty set

$A_{x}$ with high probability. ...
more >>>

Daniel Dewey

We give evidence for a stronger version of the extended Church-Turing thesis: among the set of physically possible computers, there are computers that can simulate any other realizable computer with only additive constant overhead in space, time, and other natural resources. Complexity-theoretic results that hold for these computers can therefore ... more >>>