Complexity Year in Review 2019

Some great theorems this year including non-deterministic double exponential time by quantumly entangled provers and integer multiplication in O(n log n) time. But the result of the year has to go to a paper that gave a shockingly simple proof of a major longstanding conjecture.

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture by Hao Huang

Of course 2019 will be remembered in some circles for giving us Google's claims of quantum supremacy and all the quantum hype, deserved and otherwise, that goes with it.

Personally Bill came out with his new book Problems with a Point; Exploring Math and Computer Science co-authored with Clyde Kruskal (Amazon, blog posts). Lance became a dean. 

We remember Michael Atiyah, Elwyn Berlekamp, Charles van Doren, Ray Miller, Jérôme Monnot and Nils Nilsson.

Thanks to guest posters Abhinav Deshpande, Evangelos Georgiadis, Samir Khuller, Ming Lin, David Marcus, Ben Shneiderman and John Tromp.

As we move into the 2020s, we tend to look back and look forward. The 2010s will go down as the decade computing and data transformed society, for better and worse. Google turned 21 this year as its OG leadership stepped down. I turned 21 in 1984, but 1984 seems closer than ever.

Last year we ended the year in review by 

We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.

2019 was not quiet and we're about to head into an impeachment trial, Brexit and a critical US presidential election. The real challenges of the twenties will come from massive transformation from automation, climate change and deepening divisions in our society. How will academia cope with changing demographics, financial challenges and educating to manage the technological revolution?

Let's all take a deep breath, roll up our sleeves and get the decade going.