Theoretical computer science
Short algorithm, long-range consequences
March 1, 2013
A new technique for solving ‘graph Laplacians’ is drastically simpler than its predecessors, with implications for a huge range of practical problems.
Demaine named Presburger Award recipient
February 25, 2013
Professor Erik Demaine was cited for his contributions to computational geometry and data structures.
Proving quantum computers feasible
November 27, 2012
With a new contribution to probability theory, researchers show that relatively simple physical systems could yield powerful quantum computers.
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: Computational complexity theory, Cryptography, Encryption, Interactive proofs, Quantum computing
Dueling algorithms
March 18, 2011
If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.
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?
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.
Subscribe
