Theoretical computer science

News Search Form (Theoretical computer science)

1 - 7 of 7 Articles
  • 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.

    March 1, 2013
  • Demaine named Presburger Award recipient

    Professor Erik Demaine was cited for his contributions to computational geometry and data structures.

    February 25, 2013
  • Proving quantum computers feasible

    With a new contribution to probability theory, researchers show that relatively simple physical systems could yield powerful quantum computers.

    November 27, 2012
  • 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
  • Dueling algorithms

    If software companies design their algorithms with the sole intention of outperforming each other, the customer can be the loser.

    March 18, 2011
  • 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
  • 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