| 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. |
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.