Theoretical computer science
Short algorithm, long-range consequences
March 1, 2013A 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, 2013Professor Erik Demaine was cited for his contributions to computational geometry and data structures.
Proving quantum computers feasible
November 27, 2012With 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, 2012Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.
March 18, 2011If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.