It’s kind of funny that the article calls the field of computational complexity “arcane”, considering it is at the forefront of everything we know about the lim

It’s kind of funny that the article calls the field of computational complexity “arcane”, considering it is at the forefront of everything we know about the limits of computing. That said, I haven’t understood the intense, long term focus on worst-case case and average-case analysis within the field. In fact, when I first heard of big-O notation many years ago, it took me an embarrassingly long time before I realized this referred to the asymptotic performance of an algorithm on the worst-case instances of a problem. I remember thinking “Why on earth would you care about that? You can derive pathological examples to just about anything.” Even the term “average-case” is misleading. We’re not talking about “average” in the sense of a typical instance of a problem class one might encounter in the course of daily life. This instead refers to the expectation value of the algorithm’s (asymptotic) performance over all problem instances within a formal language. Sure, the non-colloquial usage of the term “average” here is obvious to mathematicians, but I don’t think someone outside the field is likely aware that we see drastically better performance of heuristic algorithms on real-world instances of NP-hard problems than one would expect based upon a naive review of the research from computational complexity theory. This performance gap between theory and practice is due to the fact that the problems we encounter in daily life have such a huge amount of mathematical substructure to them, and I would be very surprised if a provably optimal average-case algorithm ever realistically corresponds to the mean performance of an algorithm optimally tailored to the distribution of problem instances we encounter in real world data. Consider matrix factorization. There are techniques that speed this up considerably if the matrix is known to be positive semidefinite, sparse, low-rank, and so on. Who knows how much undiscovered substructure is lurking in the set of real-world problem instances we lump together under “matrix factorization”. The subfield of computational complexity theory that moves beyond overall complexity analysis I believe is called BWCA, “Beyond Worst-Case Analysis” (but someone correct me if that’s not right). For mathematical objects like neural networks, where the specific problem instances have an absolutely massive amount of hidden substructure within them, I think we will have to use approaches like BWCA going forward to learn more about the nature of e.g., transformers. My view is that we should focus less on the absolute limits of a particular architecture (woohoo, it’s Turing complete and a universal function approximator like everything else) and drill down more into studying the limits of the interplay between model architecture and the intrinsic hidden substructure of the data that the model is trained on.