A Trip Down Memory Lane: Eric Allender on asy lower bounds and isomorphism

I recently came across (by accident) the link to all of the BEATCS complexity columns from 1987 to the 2016. See HERE. (If you know a link to a more recent webpage then email me or make a comment. There is a link to all of the issues of BEATCS here; however, I want a page with just the complexity  theory columns.)

This gave me a trip down memory lane and a series of blog posts: Briefly describe an  articles and also get commentary from the original authors on what they think now about the area now.

First up: Eric Allender

62 and 66) Some pointed questions concerning asymptotic lower bounds and news from the isomorphism  front by Eric Allender,   1997 and 1998. The article I point to is a later article that combined both articles.  This paper  is about why Asymptotic Lower Bounds ARE relevant to real computations, and also why the isomorphism of complete sets is relevant
to real computations. I asked Eric about (a) how do people outside of theory regard lower bounds today, and (b) any more news on the isomorphism front?

Here's my answer to question (a):

Sadly, one still frequently runs into folks who contend that complexity theory has no value for practitioners.  I wish that people who hold those views would read my article, and -- if they find it unpersuasive -- that they would put forward some new, more convincing arguments about why complexity theory is useless, rather than trotting out the same old "straw man" arguments that I so effectively destroy in this article (in my own humble opinion).

The article was written for a general audience, but I don't think that it ever reached the audience I had in mind.  Google Scholar says that it was cited 8 times by authors other than myself -- and some of those 8 are duplicates.

Re-reading the article, I think that it's aged fairly well, although there are few things that are a bit out-of-date.  For instance, in Section 2, I describe the paucity of meaningful conditional lower bounds on the time-complexity of problems in P.  The development of fine-grained complexity theory has done a lot to fill in this gap in our understanding.  And parameterized complexity (which gets a brief mention in this same paragraph)  has a much bigger footprint than when I wrote the article.

Of course, there have been some significant developments, regarding Graph Isomorphism (e.g., Babai's work).  And in Section 5, I say that it's open if Ntime(2^n) is in AC^0[6], but Williams settled that question.

There are still not very many examples of concrete circuit lower bounds for reasonable-sized inputs, of the type that I cite from Stockmeyer's thesis (which finally appeared in a J.ACM article some 28 years after Stockmeyer got his PhD).  I was able to find exactly one new result in this direction, by Wesolowski and Williams, see here

Here is my answer to (b) 

 The biggest news on this front is Manindra Agrawal's spectacular isomorphism theorem (JCSS 2011), which improves on the \(AC^0\)-isomorphism results that are discussed in the paper.  (He gives a completely uniform isomorphism theorem, which avoids the uniformity issues in the earlier results showing that complete sets are \(AC^0\)-isomorphic  Manindra also wrote an excellent survey on the isomorphism conjecture see here.  More recently, there has also been some nice work, discussing isomorphisms via reductions more powerful than poly-time: (Harkins, Hitchcock, and Pavan, FSTTCS 2007 and Computability (the journal of the Association CiE) 2014).

My article tries to make a point, saying that isomorphisms might be useful in showing that the factoring problem is not complete for any "standard" complexity class.  Upon some more reflection (and discussions with Michal Koucky) I came to see that some of the approaches I suggested are probably not very workable.  I discuss this in another survey I wrote, see here.