Complexity result of the year goes to
Consider the following version of Occam's Razor: find the smallest program consistent with your data. Hirahara shows that solving this problem is randomly hard for NP. The paper also takes a major step to understanding the complexity of the Minimum Circuit Size Problem, a major area of study in computational complexity over the past few years.
Runner up goes to Maximum Flow and Minimum-Cost Flow in Almost-Linear Time by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva. The title speaks for itself.
In the computing world, 2022 has become the year of machine learning taking over. It seemed like almost every week we saw a new ML breakthrough from AlphaTensor, improving on Strassen, to AlphaFold mapping out the structure of nearly every known protein. AI generating new text, pictures and code and playing Diplomacy. Not to mention ChatGPT that will disrupt education and everything else. Enough to almost make us forget the tech layoffs and the downfall of Twitter as we know it.
We remember Fred Brooks, Juris Hartmanis, Joel Moses, Rolf Niedermeier, Alexander Vardy, Gerhard Woeginger and Fastlane.
Thanks to our guest posters Boaz Barak, David and Tomas Harris, Jonathan Katz, David Marcus, Jelani Nelson, Prahalad Rajkumar and Aravind Srinivasan.
Bill and I wish you the best for the holidays and look forward to keeping you informed and entertained with minimal AI assistance.
No comments:
Post a Comment