Computational complexity theory

News Search Form (Computational complexity theory)

1 - 7 of 7 Articles
  • The complexonaut

    Scott Aaronson travels the far reaches of computational complexity, shaping conventional and quantum computing.

    April 7, 2014
  • 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.

    January 18, 2013
  • 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.

    July 31, 2012
  • Algorithmic incentives

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

    April 25, 2012
  • 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?

    August 17, 2010
  • What computer science can teach economics

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

    November 9, 2009
  • 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.

    October 29, 2009