Efficient algorithms, the Exponential Time Hypothesis, and losing the plot (argmin.net)

I’ve seen quite a few critiques of the practicality of time complexity analysis but I’ve never seen an article describe what we should replace it with. Time complexity analysis, as given, has given some structure to the infinite zoo of problems even if imperfect and composes relatively nicely and is relatively simple. It’s also tractable, has mathematical structure, and is often practical as a heuristic (the kinds of algorithms people typically encounter or come up are typically reasonable under this kind of analysis). In order to be a proper substitute, something would have to satisfy all these qualities. Without such a substitute, we are back to analyzing problems and their complexity without any sort of framework which seems even worse than just remembering that sometimes the big O is not practical.

The only candidate that would be more practical that I know of is cache complexity for cache oblivious algorithms but that’s much more complicated.

That's a very long-winded way of saying "I'm an ultrafinitist"...

I guess in engineering what you care about is: how fast is it on given input size X relevant for the practical problem. Or: how much input size can we do in time bound Y.

This is another rant about the author's bugaboo.

It would be great to prove that there is or isn't a non-galactic polynomial-time algorithm for NP-complete problems. But we can't even solve the easier problem of proving there is or isn't a galactic polynomial-time algorithm, so what hope is there for the harder problem?

If you could prove that any polynomial-time algorithm for NP problems had to be galactic, you would be the most celebrated computer scientist since Turing. It's just no one has any idea how to do that.

Would be great to get at least a glimpse of an understanding about why the algorithm does the enumeration in the first place.

Surely it cannot be necessary for the complexity result?!

This reminds me of the (perhaps unrelated meme) hello I would like (graph of zeta function) number of apples. Statements dreamt up by the utterly deranged.

Indeed I have met professors who claim since something is O(1) it doesn't matter if you run it 4 times. No need to optimize. I think it's just part of the wider divide between theory and application. For instance big O also requires a register machine to make sense, which most courses don't define. Somehow addition and multiplication are O(1) in some places and O(n) or O(n^2) somewhere else. Also quite common is the fact that sets are slower than lists for lookup for small n, despite being O(1).

It's just a tool and we shouldn't miss the trees for the forest. I also understand this comment has nothing to do with the ETH or the article, but just some thoughts I have after reading the first chunk on complexity

I don't think the author's criticism of "Big-O Cabal" is very nuanced, but to the second half of the essay it is funny/concerning/sobering to find that the OpenAI proof is doing brute-force search for all instances below some super-astronomic threshold. It kind of buries the lede if the proof did not mention this clearly and the author has to comb through it to find out (I asked ChatGPT the same on the pdf file, but it came up with some other threshold number).

Post #1,000,037 complaining about AI in math by ragging on the existence of pure math. Sigh.

Well, since no one has sided with the author, let the math coin clipping keep going without pause.

Author is a math professor who somehow wants you to believe that he didn't know what a computational model is until OpenAI's manuscript dump a few days ago. In this post, he now extends that pretending game to galactic algorithms.

Very gonzo, but maybe I prefer to learn about these things with a little less circlejerk.