FOCS 2022 – Inside the Denver Gathering That Quietly Shaped a Decade of Computer Science

A theoretical computer science conference has an almost antiquated feel to it. People travel from all over the world, sit in hotel ballrooms with subpar coffee, and watch as others present proofs on slides that hardly anyone in the audience can follow in real time. That was precisely what happened at FOCS 2022, which took place in Denver from late October through early November. However, as the schedule developed over those four days, it was difficult not to sense that something real was taking place—a field recovering from two bizarre pandemic years and rediscovering what it truly looks like to debate a result in person.

A portion of the story is revealed by the numbers. The program committee chose 110 of the 296 submissions for presentation, a roughly 37 percent acceptance rate that falls comfortably within the conference’s historical range. The program committee, led by Jelani Nelson, convened via video conference from June 27 to June 30 following what the preface refers to as an intense period of electronic discussion. The texture of those lengthy PC meetings is familiar to anyone who has witnessed them: protracted debates over dubious papers, abrupt alliances formed over a clever lemma, and the quiet exhaustion of trying to be fair to 296 sets of authors at once.

Although a few clusters stood out, the accepted papers covered the typical range. A paper by Shaltiel and Silbak on error-correcting codes achieving BSC capacity against polynomial-size circuit channels, as well as work on binary codes resilient beyond the classical 1/4 bound, demonstrated the strength of coding theory. Additionally, quantum results seemed unusually prominent. Yamakawa and Zhandry’s work on verifiable quantum advantage without structure came at a time when the general public had finally begun to care, if vaguely, about what quantum computers might actually accomplish. Jiayu Zhang’s paper on classical verification of quantum computations in linear time sparked genuine discussion in the hallways.

Denver itself was an odd host. A few guests were taken aback by the thin mountain air. For a community more used to the windowless function rooms of generic convention centers, the view of the Rockies in the distance on clear mornings outside the venue felt almost theatrical. Managing the local arrangements, Alexandra Kolla appears to have made thoughtful pacing decisions; there were appropriate breaks, time for conversation, and the kind of unstructured space that virtual conferences had long since taken away.

It’s possible that FOCS 2022 will be viewed by field historians as a transitional rather than a pivotal event. There wasn’t a single significant outcome that everyone thought would change the field. Rather, a slower process was taking place: the steady, nearly unyielding advancement of a community that has worked for decades to solve issues that defy simple intuition. Lower bounds for submodular function minimization became more precise. SDP solvers became quicker. Of all things, a near-linear time sampler for general constraint satisfaction was obtained for the Lov α local lemma.

I get the impression that theoretical computer science is in one of its more subdued, self-assured stages as I watch the program go by. Not ostentatious. not pursuing media attention. simply carrying out the task. It’s really unclear if that will continue as machine learning continues to draw attention and funding from other sources. However, it didn’t seem to matter much for those four days in Denver, where the mountains were visible through the lobby windows.