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


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


Nima Anari | Frank Ban | Antonio Blanca | Brielin Brown | Jonah Brown-Cohen | Paul Christiano | Fotis Iliopoulos | Marc Khoury | Jingcheng Liu | Urmila Mahadev | Peihan Miao | Anupam Prakash | Christos-Alexandros Psomas | Aviad Rubinstein | Manuel Sabin | Aaron Schild | Tselil Schramm | Jarett Schwartz | Sara Sheehan | Jonah Sherman | Seung Woo Shin | Di Wang | Guoming Wang | Benjamin Weitz | TongKe Xue

Alessandro Chiesa | Sanjam Garg | Richard Karp | Elchanan Mossel | Christos Papadimitriou | Prasad Raghavendra| Satish Rao | Jonathan Shewchuk | Alistair Sinclair | Yun Song | Bernd Sturmfels | Luca Trevisan | Umesh Vazirani

Andre Chailloux

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


This semester:

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