My Week at Simons

This week finds me at the Simons Institute for Theoretical Computer Science in Berkeley California. Simons started about the same time I joined the administrative ranks and never had the opportunity to spend a full semester there. I can manage a shorter trip and purposely chose a week with no workshops and great visitors including Sam Buss, Russell Impagliazzo, Valentine Kabanets, Toni Pitassi, Ryan Williams, former student Rahul Santhanam and former postdocs Pavan Aduri and Vinod Variyam and many others including the next generations of complexity theory leaders. Simons is having programs on Meta-Complexity and an "extended reunion" for Satisfiability. Apparently I used to work on Meta-Complexity before it was a thing.

Computational complexity traditionally has tried to get ahead of new technologies, and modelled randomized, parallel, quantum computation and cryptography in the infancy of their development allowing complexity to help guide our understanding and development of these areas. In the last twenty years or so, complexity has migrated more towards mathematics, and has mostly missed technological changes like cloud computing, hierarchical memory models, edge and mobile computing for example. 

But the recent advances in optimization and machine learning cannot be ignored. There has certainly been plenty of discussion of ChatGPT and Russell gave an informal lecture yesterday trying to model large-language models at some level. I've been having some discussions about how complexity can answer questions like what it means for a model to be explainable. 

Complexity theory also out to reckon that practically we seem to be getting the best of P = NP while avoiding losing cryptography simultaneously in Heuristica and Cryptomania among Russell's five worlds. Russell claims we're not in Heuristica, at least not now, since we can still generate hard to solve problems. But if our models aren't modeling the world we live in, perhaps it's time to rethink the models.