Complexity Year in Review

Back in the day (circa 1989) we studied locally random reductions which would lead to all those exciting interactive proof results. Somehow locally random reductions got rebranded as locally correctable codes and this year's result of the year settled a long-standing open question. 

An Exponential Lower Bound for Linear 3-Query Locally Correctable Codes

Pravesh Kothari and Peter Manohar

Roughly if you want a code where each bit is a linear combination of three other appropriately-chosen random bits with constant error, you're going to need a very long code. More in Quanta. 

Things Bill wanted me to mention in this post: R(5), new Mersenne prime, Busy Beaver, Vazirani's delayed proof, formal verification of the sum-check protocol and AI song generation.

2024 was quite a year, we saw a computational complexity theorist, Avi Wigderson, win the Turing Award and computer scientists win Nobel Prizes in both chemistry and physics. Also some elections, wars and college protests. It's all a prelude to a perfect storm for US higher education with the oncoming trains of the new administration, artificial intelligence, fiscal challenges and the demographic cliff. Hang on tight, it's going to be a bumpy ride.

We remember Rance Cleaveland, Peter Higgs, Thomas Kurtz, Phil Lewis, Steven Rudich, Frank Ryan, Jim Simons, Luca Trevisan, Dominic Welsh and Niklaus Wirth.

We thank all our guest posters and collaborators Eric Allender, Martin Bullinger, Max Burkes, James De Santis, Mohammad Hajiaghayi, Neil Immerman, Valentine Kabanets, Harry Lewis and Larry Washington.

Enjoy the holidays and we'll see you in January.