{\huge }

{\it\huge Let's Mention Foundations}

Congratulating Dick on the 2014 Knuth Prize \vspace{.5in}

Dick Lipton of course is the founder and driving writer of this weblog. He is also a computer scientist with a great record of pathbreaking research. The latter has just been recognized, I am delighted and proud to say, with the award of the 2014 Knuth Prize. The prize is awarded jointly by the ACM Special Interest Group on Algorithms and Computation Theory and the IEEE Technical Committee on the Mathematical Foundations of Computing, and was instituted in 1996, shortly after the formal retirement of the great---and very much active---Donald Knuth.

Today I am glad to give my congratulations in public, and also thanks for a wonderful and long association.

Only in reading around while writing this post did I learn that Dick won another major honor earlier this year: election to the American Academy of Arts and Sciences. The end of April was crazy with personal and unusual professional matters for both of us, and it didn't come up. In the 2014 list for CS he is alongside Jennifer Chayes, Ron Fagin, David Harel, Daphne Koller, Leslie Lamport, Leonid Levin, and Mendel Rosenblum.

The Knuth Prize is ``for outstanding contributions to the foundations of computer science.'' The description also says it may be partly based on educational contributions such as textbooks and students, but ``is not based on service work for the community, although service might be included in the citation for a winner if it is appropriate.'' The ACM release does not mention this blog. So I will follow an imitation of Basil Fawlty's advice in a famous episode of the immortal 1970's BBC TV sitcom ``Fawlty Towers'':

Don't mention the blog.

But I will mention foundations, since that is an aspect of the recognition that comes with a price but is a longstanding purpose of this----wait, don't mention the...

Ideas and Foundations

The release includes some of Dick's major contributions, and some others have been noted on StackExchange. I can add the first work by Dick that I was aware of: two papers in 1979--80 with Rich deMillo---also now at Georgia Tech---which were part of various efforts to answer questions about $latex {\mathsf{P =?\;NP}}&fg=000000$ via logic and model theory. There is also his involvement with time-space tradeoffs for $latex {\mathsf{SAT}}&fg=000000$, which represent the best lower bounds---well in a broad sense ``kind-of'' lower bounds---known for any major $latex {\mathsf{NP}}&fg=000000$-complete problem. Most recent and potentially important in my purview---but you might have to comb through his DLBP page to realize they're there---are papers on multivariable polynomials modulo composite numbers, which are at the frontier of circuit complexity lower bounds.

What generates all this is a powerful beacon of ideas that have had a photoelectric effect on many parts of computer science, more than a typical theoretician encounters. I should know---it has been my privilege to do radiographic processing for many more, even some that haven't yet appeared on this---oops---anyway, more ideas than I can often keep up with. Not to mention that I'm also pursuing (and opening) some ideas of my own. The point is that these ideas are almost all aimed at foundations. The examples above are aimed at foundations of complexity theory. That goes double for some ideas that haven't progressed well, at least not yet.

The Problem

The problem---with the problem and much more---is the foundations of complexity are set in sturdy concrete. They basically haven't budged. Beams of ideas bounce off or just get absorbed. Major related parts of algorithms and crypto and other fields are likewise shielded. This is polar the opposite situation of what Bill Thurston recounted about his field of manifold foliations in his famous essay, ``On Proof and Progress in Mathematics.''

The difficulty of direct progress has been so discouraging that through the theory applications grapevine I've heard whispers that one can phrase as, ``Don't mention foundations...'' We tried to present aspects of this more positively in a recent post featuring Chayes.

However, if you aim a beam hot enough and keep it focused for long enough, events do happen. The question should not be whether it's worth aiming the beam, but rather what is needed to establish and maintain the intensity and focus. What we suspect is that just as in particle physics, a century on from when the likes of Joseph Thomson and Ernest Rutherford and Robert Millikan could work alone or with one associate or two, progress will require greater co-ordination of multiple researchers and shared focus on ideas than our field is yet accustomed to. Hence...well, we can mention that various people we know and admire are trying to foster this in their own ways, both activated and proposed.

As I said, aiming at foundations has a price---and the payment is alas more evenly distributed among those who try than the rewards. That's why it is good to remember that ever so often, in small as well as big, a prize comes with the price. The above, too, has an added price, but perhaps it will be ushered in with a new model for appreciating the credits.

Open Problems

The Knuth Prize has the unusual period of being awarded every 1-1/2 years officially. The last five awards are dated 2010, 2011, 2012, 2013, and now 2014. Can this seeming contradiction be resolved mathematically? Perhaps the ``1-1/2'' is governed by left-and-right approximands in the manner of John Conway's surreal numbers, which Knuth described in an engaging book. A left-bound of 1.25 would just barely allow it. However, we suspect that any such involvement by Knuth would have instead fixed the period at $latex {2^9 = 512}&fg=000000$ days, and then we don't see a solution...unless maybe arithmetic is inconsistent after all.

Of course we congratulate Dick without any inconsistency.