Letter from the Director, February 2021

Dear friends,

A new year is now underway, and we look forward to seeing many of you in person soon.

Last month, we kicked off our Spring 2021 programs, Satisfiability: Theory, Practice, and Beyond and Theoretical Foundations of Computer Systems. 

The classical theory of NP-completeness predicts that testing satisfiability of Boolean logic formulas is intractable in the worst case. However, satisfiability problems that one encounters in real-world applications are often not worst case and can be solved efficiently. In fact, the last two decades have seen the development of exceedingly efficient algorithms for many of these problems, perhaps most impressively in the form of so-called SAT solvers for logic formulas. The satisfiability program brings together researchers from complexity theory, logic, and computational algebra, among others, to work toward a theory of satisfiability in the real world and to further algorithmic progress.

Synergistic to the satisfiability program, the computer systems program is concerned with the use of satisfiability and model checking toward building and analyzing computer systems. Areas of investigation include new developments in logic and automata, probabilistic modeling in the analysis of systems, the use of games and their equilibria, and techniques for the analysis of cyber-physical systems. 

The programs are creatively working across the logistical challenges of collaborating in an online environment. Workshops in the programs are being spread over the semester, instead of being scheduled within a week. Large-scale online collaborations among the participants in the form of polymath projects are already underway. At last count, six reading groups on various topics were being organized in the programs.

Meanwhile, the weekly Quantum Colloquium talks have been a big success in bringing a series of illuminating survey talks on quantum computation to the broader CS community. In the past few weeks, the Quantum Colloquium has featured talks by Aram Harrow, Scott Aaronson, Nathan Wiebe, and Dorit Aharonov and has attracted upward of 250 participants from across the world. The talks offer plenty of time for questions and discussion, as well as an opportunity to meet and hang out with colleagues on Gather.town before and afterward.

In this issue of the newsletter, we share a talk that Jon Kleinberg gave in our Theoretically Speaking public lecture series in 2016 — Mapping the Online World: Social Connectedness in the Digital Age. And we invite applications for our Science Communicator in Residence Program. 

May this year be one of renewal and many happy reunions.

Best wishes,
Shafi

Shafi Goldwasser
Director, Simons Institute for the Theory of Computing