Computational complexity theory

Research update: Multiple steps toward the ‘quantum singularity’

January 18, 2013

Over three days in December, four research groups announced progress on a quantum-computing proposal made two years ago by MIT researchers.

Also labeled: Quantum computing, Linear-optical quantum computing, Computer Science and Artificial Intelligence Laboratory (CSAIL), Computing, Optical computing, Faculty, Graduate, postdoctoral, Research, Probability, Collaboration

10-year-old problem in theoretical computer science falls

July 31, 2012

Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.

Also labeled: Cryptography, Encryption, Interactive proofs, Quantum computing, Theoretical computer science

Algorithmic incentives

April 25, 2012

A new twist on pioneering work done by MIT cryptographers almost 30 years ago could lead to better ways of structuring contracts.

Also labeled: Computer science and technology, Crowdsourcing, Cryptography, Electrical engineering and electronics, Mathematics, Interactive proofs, Zero-knowledge proofs

3 questions: P vs. NP

August 17, 2010

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?

Also labeled: Explained, Theoretical computer science, P vs. NP

What computer science can teach economics

November 8, 2009

Constantinos Daskalakis applies the theory of computational complexity to game theory, with consequences in a range of disciplines.

Also labeled: Computer science and technology, Computer Science and Artificial Intelligence Laboratory (CSAIL), Electrical engineering and electronics, Game theory, Nash equilibrium

Explained: P vs. NP

October 29, 2009

The most notorious problem in theoretical computer science remains open, but the attempts to solve it have led to profound insights.

Also labeled: Theoretical computer science, Explained, P vs. NP