Tuesday mornings in Simonyi 101 are particularly quiet. The listening silence of a room where forty or fifty people are making a great effort to follow a single line of reasoning on a whiteboard, rather than the dead silence of a library. For years, the Institute for Advanced Study’s Computer Science and Discrete Mathematics seminar has been held in this manner, week after week, with minimal fanfare and hardly any outward effort to attract attention. However, this room consistently appears when you consider the sources of the most intriguing concepts in theoretical computer science over the past ten years.
Irit Dinur and Avi Wigderson, the program’s leaders, are well-known to anyone involved in complexity theory. Wigderson, who shared the 2023 Turing Award, has been a mainstay at the Institute for so long that the curriculum practically seems to follow his beat. Dinur presented her work on the PCP theorem, which in some ways is both one of the most well-known findings in theoretical computer science and one of the most difficult to explain at a dinner party. Observing the seminar list gives the impression that the program is more of an ongoing dialogue between individuals who have never quite stopped asking the same questions than it is an academic department.
| Information | Details |
|---|---|
| Program Name | Computer Science & Discrete Mathematics (CSDM) |
| Host Institution | Institute for Advanced Study |
| Location | 1 Einstein Drive, Princeton, New Jersey 08540, USA |
| Program Leadership | Irit Dinur and Avi Wigderson |
| Seminar Venue | Simonyi 101 (with remote access option) |
| Seminar Schedule | Mondays 11:00 AM – 12:00 PM and Tuesdays 10:30 AM – 12:30 PM |
| Founded As Part Of | School of Mathematics at IAS |
| Research Focus | Theoretical computer science, complexity, combinatorics, cryptography, graph theory |
| Affiliated Partner | DIMACS at Rutgers (joint postdoctoral track) |
| Contact | contactus@ias.edu, Phone (609) 734-8000 |
The forthcoming schedule appears to be a snapshot of the current obsessions in the field. Using themes from the now-famous MIP* = RE result by Ji, Natarajan, Vidick, Wright, and Yuen, Michael Chapman is speaking about the quantum soundness of the low-degree test. When that paper was published in 2020, it used a quantum complexity proof to subtly resolve a question that had been open in operator algebras for decades. CSDM seems to draw this kind of crossover moment.
The program’s lack of reliance on the institutional machinery that most universities rely on is what makes it unique, at least from the outside. There are no students pursuing degrees. The program’s partner since before the majority of the current postdocs were in graduate school, DIMACS at Rutgers, frequently provides joint funding for the visiting members’ one- or two-year stays. An unusually high number of individuals who go on to run their own organizations elsewhere have been produced by the DIMACS-IAS pipeline. No one at the Institute would put it that way, but it’s not a coincidence.
The talk titles alone reveal the field’s texture. Ramsey numbers, expander codes that satisfy Reed-Muller decoding, triangle-free graphs, and color-avoiding paths. Some of these seem almost recreational, but keep in mind that just two years ago, a group that included regular CSDM visitors moved the bounds on Ramsey numbers for the first time in seventy years. In this field, the distinction between a curiosity and a breakthrough is often blurred.
It’s difficult to ignore the program’s reliance on a level of patience that has become outdated practically everywhere else in the computer industry. Here, there are no product launches, demos, or metrics. Just a board, a room, and the gradual accumulation of outcomes that might or might not matter in five years. It’s genuinely unclear if that model will withstand the strain on academic funding over the next ten years. For the time being, however, Simonyi 101 chairs continue to fill up on Tuesday mornings, and someone at the board keeps beginning with, say, a graph.
