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