9
$\begingroup$

I am a research scholar who works in Algorithms and Complexity theory, I use parameterized complexity to some extent. To me it appears that researchers in parameterized complexity are very active (I don't mean that other are not) in terms of number of research papers. I have seen that researchers from communication complexity, arithmetic complexity etc. are also using various parameters to greater extent.

Question : Is parameterized complexity going to be the future of complexity theory? Future just means number of research papers, number of researchers working in that area etc.

Please note that I am naive and may not be aware of many things.

$\endgroup$
  • 3
    $\begingroup$ I think only really your second question is suitable for this site - namely, are there works on "quantum parametrized complexity"? - as the first question is (a) about predicting the future, which is always hard, and (b) the answers would be very subjective. But I suspect the answer to your question (1) is that there is still lots of active research in algorithms and complexity that is not about parametrized complexity. $\endgroup$ – Joshua Grochow Feb 25 '18 at 17:02
  • 1
    $\begingroup$ Non-researcher here, but I never knew parameterized complexity was a different thing than just... complexity. What exactly did people do beforehand when a complexity depended on two quantities? Just forget one of them? $\endgroup$ – Mehrdad Feb 25 '18 at 22:10
  • 1
    $\begingroup$ I'm a big fan of parameterized complexity and I was excited to see this post on the same day that the FPT newsletter came out. :) $\endgroup$ – Michael Wehar Feb 26 '18 at 7:17
16
$\begingroup$

Predicting the future is nigh impossible, especially so for cutting-edge research. I don't think anyone predicted how much impact deep learning is now having or that cryptography would be taken over by indistinguishability obfuscation.

That said, I will say this much: I don't see any particular reason to expect parameterized complexity to take over. It's a mature field that has been active for something like 20 years. It doesn't really strike me as an up-and-coming area. To be clear, I think it's a successful area that will continue to thrive.

If you look on google trends, search interest in parameterized complexity has been declining. (Stick in some other terms for a comparison if you're interested.) If you look up the combined citations for the Downey-Fellows textbook Parameterized Complexity and their updated textbook, you see that they are pretty stable: enter image description here (Source: Google scholar. I added both books to my own profile, merged them, took a screenshot of the combined citations, and then deleted them from my profile.)

This is a healthy number of citations, but it is not the exponential growth that would make you think parameterized complexity is going to take over. Of course, this data is very flawed, but it's the best indication I can find of the global popularity of parameterized complexity.

Note that things can be very popular locally even if they aren't popular globally. When I was an undergrad, I thought that I needed to learn about category theory because everyone around me was talking about it; I even bought a book. Then I moved on to grad school and never heard about it again; the book remains unread to this day. Perhaps you are in a similar situation -- you are in a department where there is a lot of parameterized complexity going on, but, if you move somewhere else, the story will be completely different.

$\endgroup$
  • 5
    $\begingroup$ RIP to all those unread category theory books out there... $\endgroup$ – gigabytes Feb 26 '18 at 0:25
  • 3
    $\begingroup$ Just out of curiousity: are you saying that there was a place where a number of people working in complexity and algorithms were interested for some time in category theory? Or were these people more in the programming languages world? (In which case it would not be surprising). As a category-theory-oriented researcher, I am quite curious to know where this place was and what was the interest about. $\endgroup$ – Damiano Mazza Feb 26 '18 at 11:29
  • $\begingroup$ @DamianoMazza I got into algorithms and complexity in grad school. My exposure to Category theory was on the PL/logic side of things. I do like category theory; it just hasn’t come up much in my work. $\endgroup$ – Thomas Feb 26 '18 at 16:38
  • $\begingroup$ Ok, as I said, it's not very surprising then! (Neither that PL/logic people are interestest in categories, nor that you haven't found a use for them in algorithms and complexity). Thank you! $\endgroup$ – Damiano Mazza Feb 27 '18 at 18:26
  • $\begingroup$ @DamianoMazza you can make a “pseudo-category” of TMs and quotient it by some weak reducibility and then you get nice things like the ability to characterize completeness via category theoretic constructions, but it seems to me when I’ve done it that you get exactly the same outcomes by just using a poset. There’s this paper which was posted on here a while ago making this connection: principal ideals in this poset form “syntactic classes”, which have a complete language and are countably enumerable. Maybe there is more mileage you can get from a suitable category, I haven’t gotten any though. $\endgroup$ – Samuel Schlesinger Mar 18 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.