The complexonaut
Scott Aaronson travels the far reaches of computational complexity, shaping conventional and quantum computing.
Research update: Multiple steps toward the ‘quantum singularity’
Over three days in December, four research groups announced progress on a quantum-computing proposal made two years ago by MIT researchers.
10-year-old problem in theoretical computer science falls
Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.
Algorithmic incentives
A new twist on pioneering work done by MIT cryptographers almost 30 years ago could lead to better ways of structuring contracts.
3 questions: P vs. NP
After glancing over a 100-page proof that claimed to solve the biggest problem in computer science, Scott Aaronson bet his house that it was wrong. Why?
What computer science can teach economics
Constantinos Daskalakis applies the theory of computational complexity to game theory, with consequences in a range of disciplines.
Explained: P vs. NP
The most notorious problem in theoretical computer science remains open, but the attempts to solve it have led to profound insights.