[dkarl]

So, to summarize: the article criticizes researchers who focus only on worst-case complexity. While the theory is beautiful, we can point to many problems for which it does not accurately predict performance.

I still don't get it, because it's okay for some people to be working on purely theoretical problems, motivated by mathematical curiosity and aesthetics. Is there a lack of people working on more concrete problems, bridging the gap between theory and practice? Are there outstanding problems arising from practice that are ignored because supposed "applied" researchers don't actually care about applications?

I think this criticism is a little strange, because most complexity theorists also work on "average-case" complexity

That sounds almost as theoretical as worst case to me. I would expect "applied" complexity theory to provide a theoretical framework for how a practitioner can add information that they know about how their problem differs from the aesthetically ideal problems that arise in theory. Like, my factory floor is not a frictionless plane, aha, here's how you measure a "coefficient of friction," and here's a new equation where you can see how the coefficient of friction affects the results. Or, my dataset isn't a uniformly random blob of bits, so is there a statistical property I can measure that lets me estimate the probability of the working memory of my algorithm exceeding 2.4 times the size of the input size?

[through_17]

Let me clarify: average-case does not just mean "over the uniform distribution", though that is of course one distribution of inputs we can study (mostly with applications to cryptography). Average-case complexity can be studied over any family of distributions.

Finding ways to characterize hardness and easiness in terms of underlying structure to those input distributions is exactly what average-case complexity tries to accomplish. The "holy grail" is to classify problems over efficient distribution of inputs. That is, first make the fairly reasonable assumption that the family of formulas you actually run (say) SAT-solvers on came from an efficient computation ("nature", or people coming up with problems). Then, identify properties of those distributions that you can measure and "blame" intractability on.

For example, there's a huge amount of work on these types of parameters for SAT instances. See: https://people.csail.mit.edu/rrw/backdoors.pdf

This type of work could, eventually, directly inform practice.

And of course I think it is okay for some researchers to work on purely theoretical or worst-case problems. Insights from worst-case complexity are often useful in solving the more difficult problems of average-case complexity; it is useful to know where and how the theories diverge.

Reconsidering, I guess I just don't understand the article at all. Maybe he's arguing that TCS doesn't have this problem because we have a hierarchy of theories, where worst-case complexity inspires average-case complexity inspires parameterized average-case complexity which could someday be used in the real world. Over very long timescales (think, centuries) I think complexity theory will produce practical insights.

[dkarl]

This type of work could, eventually, directly inform practice.

Are there any problems taken directly from practice that complexity researchers are working on and using as context to define shortcomings in existing theory? Maybe that's what he's talking about, expanding on theory that "could, eventually, directly inform practice" and calling that "applied research" instead of tackling practical problems directly.

[through_17]

Yeah, a lot of the work on average-case SAT is directly informed by what industrial benchmarks look like.

Further from "core complexity," a lot of the work on machine learning primitives is also directly informed by instances from practice. See the "manifold hypothesis" :

https://deepai.org/machine-learning-glossary-and-terms/manif...

[bitL]

It's like you have some problems in graph theory that are NP-Complete/Hard, so in theory you are out of luck. But if you restrict yourself to a certain type of graphs, or you change your problem from e.g. computing a chromatic number on a certain type of graphs to instead decide if for a given K such K-coloring exists, suddenly there is a polynomial algorithm. And practically-wise, you might be fine with just K={2,3,4,5} and couldn't care less about other values of K for your practical case; so while in general you can't solve it, in practice you have a fast algorithm you run 4x in a row and are done.