Complexity Year in Review 2018

Result of the year goes to

Oracle Separation of BQP and PH by Ran Raz and Avishay Tal

which we wrote about in June. This work solves one of the original open questions in quantum complexity using tools from both quantum and classical circuit complexity. How often do we see oracle results with popular articles in Quanta (ignore the hyperbolic title), The Hindu and CACM?

Runner up goes to the solution of the 2-to-2 Games Conjecture by Subhash Khot, Dor Minzer and Muli Safra early in 2018. Boaz Barak gave a nice two post overview.

In last year's review we talked about the magical breakthroughs of machine learning. This year we seemed to have moved beyond the magic to where machine learning has become a thing. We see the immense value of data and continue to struggle with the ethical challenges of collecting and acting on data, dominance of the big tech companies, training all these students who want to gain expertise in the area and trying to understand why ML works as well as it does. 

The big X-factor is China. Will competition with China spur science literacy and funding in the US like the cold war with the Soviets did? Or will isolation with China limit scientific collaboration like the cold war with the Soviets did? 

The big tech surprise was the rise of electric scooters. Georgia Tech has embraced them and it is a quick way to get around campus.

Some of the other questions I asked last year didn't have interesting answers: What will the Internet look like post-net neutrality? (too early to tell) How will the new tax code play out? (too early to tell) Where will Amazon put HQ2? (New York and DC--only surprise was picking two cities) What can quantum computers with 50 qbits accomplish? (still a good question) Will bitcoin move to $300K or 30 cents? (it dropped but still has real value)

Thanks to our guest posters Vijay Vazirani, Samir Khuller and Robert Kleinberg, and anonymous.

We remember Jean Bourgain, George H. W. Bush, Babak Farzad, Stephen Hawking, Ker-I Ko and Stan Lee.

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.