A new technique for solving ‘graph Laplacians’ is drastically simpler than its predecessors, with implications for a huge range of practical problems.
March 1, 2013Professor Erik Demaine was cited for his contributions to computational geometry and data structures.
February 25, 2013With a new contribution to probability theory, researchers show that relatively simple physical systems could yield powerful quantum computers.
November 27, 2012Interactive proofs — mathematical games that underlie much modern cryptography — work even if players try to use quantum information to cheat.
July 31, 2012If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.
March 18, 2011After 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, 2010The most notorious problem in theoretical computer science remains open, but the attempts to solve it have led to profound insights.
October 29, 2009