We had an incredible year for theorems in 2015, the strongest year in computational complexity in the last decade. Topping the list as the theorem of the year is László Babai's quasipolynomial-time algorithm for graph isomorphism. A little risky because nobody, including Babai himself, has fully verified the proof but given Babai's reputation and the warm reception of his lectures, I have little doubt it will all work out. Again I strongly recommend watching the video of Babai's first lecture. Not only is Babai a great researcher but he's an excellent speaker as well. For the those up to the challenge, the paper is now available as well.
Beyond Babai's result we had a great year including random oracles separating the polynomial-time hierarchy, the (3+1/86)n size lower bound for general circuits, Terry Tao's solution to the Erdős discrepancy problem, explicit constructions of Ramsey Graphs and new bounds on threshold circuits.
We celebrated 50 years of computational complexity and Moore's law, the centenary of Hamming and the bicentenaries of Ada Lovelace and George Boole, the latter giving us the Boolean algebra. In 2016 we will celebrate the centenary of the person who used those bits to describe information.
We thank our guest posters Dylan McKay and Thomas Zeume. Dylan's metric group problem is still open if anyone wants to try and crack it.
In 2015 we continue to see CS departments struggle to meet the demand of students and industry. US universities faced many difficult challenges including dealing with race relations, freedom of speech and safety issues. Too much tragedy in the US and abroad, and a far too divisive political campaign. Here's hoping for reason to prevail in 2016.
We remember Gene Amdahl, Alberto Apostolico, Barry Cooper, George Cox, Jiří Matoušek, John Nash, Leonard Nimoy, Hartley Rogers Jr., Donald Rose, Karsten Schwan and Joe Traub.
Wishing everyone a Happy New Year and a successful 2016.