Thursday, December 23, 2021

Complexity Year in Review 2021

The pandemic hampered many activities but research flourished with a number of great results in complexity. Result of the year goes to

Locally Testable Codes with constant rate, distance, and locality by Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky and Shahar Mozes
and independently in
Asymptotically Good Quantum and Locally Testable Classical LDPC Codes by Pavel Panteleev and Gleb Kalachev

They achieved the seemingly impossible, a code that can be checked with constant queries, constant rate, constant distance and constant error. Here's Irit's presentation, a Quanta article and an overview by Oded Goldreich. Ryan O'Donnell presents the Panteleev-Kalachev paper, which also resolved a major open question in quantum coding theory.

Other great results include Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits by Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas, The Complexity of Gradient Descent by John Fearnley, Paul W. Goldberg, Alexandros Hollender and Rahul Savani, Slicing the Hypercube is not easy by Gal Yehuda and Amir Yehudayoff, and The Acrobatics of BQP by Scott Aaronson, DeVon Ingram, and William Kretschmer. The latter paper answers a 16-year old open question of mine that suggests you cannot pull out quantumness like you can pull out randomness from a computation.

In computing overall, the story continues to be the growth in machine learning and the power of data. We're entering a phase where data-driven programming often replaces logic-based approaches to solving complex problems. This is also the year that the metaverse started to gain attention. Too early to know where that will take use, but the virtual space may become as disruptive as the Internet over the next decade, and its potential effect in research and education should not be ignored. In the next pandemic, we may wonder how we survived earlier pandemics without it.

The NSF might be going through some major changes and significant increases, or not, especially with the Build Back Better bill on hold. The Computing Research Policy Blog can help you through the morass. 

We remember Matthew Brennan, Benny ChorAlan HoffmanArianna Rosenbluth, Walter SavitchAlan Selman, Bob Strichartz and Stephen Wiesner

We thank our guest posters Paul BeameVarsha Dani, Evangelos GeorgiadisBogdan GrechukDavid Marcus and Hunter Monroe.

In May I posted on emerging from the pandemic. Then came Delta. Now comes Omicron pushing us back online next month. I hope Pi-day doesn't bring us the Pi-variant.

Wishing for a more normal 2022.


  1. Hi Lance, could you revise your post? Your result of the year was independently obtained by Panteleev and Kalechev as well (while at the same time resolving a major open question in quantum coding theory):

    1. Thanks Ryan. I didn't know about the other paper.