Chasing complexity
Ryan Williams has taken a key step toward solving the biggest problem in theoretical computer science.
Theory of Computation Group
Protecting privacy in genomic databases
System helps ensure databases used in medical research will not leak patients’ personal information.
“Super Mario Brothers” is hard
Analysis shows popular video game is among the hardest problems in the “complexity class” PSPACE.
Computer science meets economics
Constantinos Daskalakis adapts techniques from theoretical computer science to game theory.
3Q: Scott Aaronson on Google’s new quantum-computing paper
Google experiments suggest that the D-Wave computer exploits quantum phenomena.
A basis for all cryptography
A tool that would provide a secure foundation for any cryptographic system may be close at hand.
Longstanding problem put to rest
Proof that a 40-year-old algorithm is the best possible will come as a relief to computer scientists.
