theory at berkeley

Berkeley is one of the cradles of modern theoretical computer science. Over the last thirty years, our graduate students and, sometimes, their advisors, have done foundational work on NP-completeness, cryptography, derandomization, probabilistically checkable proofs, quantum computing, and computational game theory. The mild weather, the celebrated coffeeshops, and eateries and the friendly and collaborative atmosphere in the group are known to be conducive to great theory-building and problem-solving. Once a week, our group comes together for the theory lunch, an event featuring an informal whiteboard presentation, the participation of our friends from Statistics and Math (and, occasionally, Physics and Chemistry) and much mingling. TGIF, the informal student seminar, which is off-limits to faculty, provides a comfortable space for students to learn about each others work.

Some of our current focus is on using computation as a lens to the sciences. Like probabilistic thinking in the last century, computational thinking will give mathematics and the sciences a new language to use and the ability to formulate new fundamental questions. We are studying the applications of theoretical computer science in many sciences, from economics (with our work on computational game theory and mechanism design) to physics (with our work on random structures and quantum computing), biology and pure mathematics (especially geometry, functional analysis and additive number theory). The core problems in algorithms and complexity remain, of course, dear to our hearts.

read more:

Sara Robinson on theory as a lens to the sciences
Michael Chabon on living in Berkeley
Luca Trevisan on doing theory in Berkeley

seminars

Special conference on Theory of Computation as a Lens on the Sciences, May 7-8, 2011

Theory Seminar on Mondays, 4-5pm, Wozniak Lounge
EconCS Seminar
Quantum Reading Group
TGIF, on Fridays, naturally.

people

Students:
Nima Anari | Anand Bhaskar | Antonio Blanca | Ma'ayan Bresler | Brielin Brown | Jonah Brown-Cohen | Paul Christiano | James Cook | Urmila Mahadev | Anupam Prakash | Christos-Alexandros Psomas | Aviad Rubinstein | Tselil Schramm | Jarett Schwartz | Sara Sheehan | Jonah Sherman | Seung Woo Shin | Piyush Srivastava | Di Wang | Guoming Wang | Benjamin Weitz

Faculty:
Richard Karp | Elchanan Mossel | Christos Papadimitriou | Prasad Raghavendra| Satish Rao | Jonathan Shewchuk | Alistair Sinclair | Yun Song | Bernd Sturmfels | Umesh Vazirani

Postdocs:
Andre Chailloux | Varun Kanade |

Recent alumni:
Andrew Chan | Siu Man Chan | Siu On Chan | Anindya De | Ilias Diakonikolas | Omid Etesami | Rafael Frongillo | Luqman Hodgkinson | Bonnie Kirkpatrick | Alexandra Kolla | Henry Lin | Lorenzo Orecchia | George Pierrakos | Daniel Preda | Grant Schoenebeck | Meromit Singer | Yaron Singer | Isabelle Stanton | Alexandre Stauffer | Madhur Tulsiani | Gregory Valiant | Paul Valiant | Thomas Vidick | Tom Watson | Chris Wilkens | Virginia Vassilevska Williams


courses

This semester:

From the past:
Here are some fun courses from the last few years. Follow the link for contents and notes.