[PollardsRho]

I don't think it's controversial to say that asymptotic analysis has flaws: the conclusions you draw from it only hold in the limit of larger inputs, and sometims "larger" means "larger than anything you'd be able to run it on." Perhaps as Moore's law dies we'll be increasingly able to talk more about specific problem sizes in a way that won't become obsolete immediately.

I suppose my question is why you think TCS people would do this analysis and development better than non-TCS people. Once you leave the warm cocoon of big-O, the actual practical value of an algorithm depends hugely on specific hardware details. Similarly, once you stop dealing with worst-case or naive average-case complexity, you have to try and define a data distribution relevant for specific real-world problems. My (relatively uninformed) sense is that the skill set required to, say, implement transformer attention customizing to the specific hierarchical memory layout of NVIDIA datacenter GPUs, or evaluate evolutionary optimization algorithms on a specific real-world problem domain, isn't necessarily something you gain in TCS itself.

When you can connect theory to the real world, it's fantastic, but my sense is that such connections are often desired and rarely found. At the very least, I'd expect that to often be a response to applied CS and not coming first from TCS: it's observed empirically that the simplex algorithm works well in practice, and then that encourages people to revisit the asymptotic analysis and refine it. I'd worry that TCS work trying to project onto applications from the blackboard would lead to less rigorous presentations and a lot of work that's only good on paper.

[LegionMammal978]

Average-case complexity can be a fickle beast. As you say, the simplex algorithm for LP is great in practice, so it's rarely problematic to use. But meanwhile, people also say, "Modern SAT/SMT solvers are great, they can solve huge problems!" Yet when I try using one, I usually run into exponential runtimes very quickly, especially for unsatisfiable instances.

Overall, it's annoying to tell whether an NP-hard problem is always really hard, or if ~all practical instances can be solved with a clever heuristic. It doesn't help that most problems receive little attention (e.g., to find solvable special cases) after being labeled NP-hard.

[aleph_minus_one]

> most problems receive little attention (e.g., to find solvable special cases) after being labeled NP-hard.

Since I know quite some people who exactly work on this kind of problem of finding special classes that can be solved in polynomial time, my impression is of course different.

But I think it can be said that if some NP-hard problem is very important in practice and there is no easy way to to get around this problem (i.e. it will also be practically relevant in, say, 15 years), the problem will for sure get a lot more attention.

This is also the reason why some NP-hard problems are much more researched than others.

[pfdietz]

I found SMT solves were stymied by merely running into cubic runtimes.

[antics]

I just meant that there are lots of problems where I think TCS could have contributed but didn't, because the relevant analysis was not acceptable at FOCS or SODA (or whatever). A good example is the original transformers paper, which is vastly over-complicated relative to (say) a later treatment[1] by Ruslan Salakhutdinov's lab, which shows that attention is "just" plain-old Nadaraya-Watson kernel smoothing—which if you don't know is a weighted average of points covered in elementary grad stats.

I'm not saying it was TCS people would be "better" at discovering this or anything like that, I'm just saying that the opportunity for contribution from TCS people is very high, and because the fields are not well-integrated you often have to wait years to uncover what ML concepts "really" are. I think working together would benefit both ML and TCS!

[1]: https://arxiv.org/pdf/1908.11775