Let’s Mention Foundations
Congratulating Dick on the 2014 Knuth Prize
|
|
Cropped from source |
Dick Lipton is of course 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 my 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 just for now I will imitate 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 
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 that 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’s 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 this…well, we can mention that various people we know and admire are trying to foster this in their own ways, not just proposed but some activated to a wonderful degree.
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, I suspect that any such involvement by Knuth would have instead fixed the period at 
Of course we congratulate Dick without any inconsistency.
Reblogged this on Pink Iguana and commented:
nice
Incidentally, this is my
single-author post. In mid-November last year, Pip (our joint-author name) and I were tied at 62. Our intent was for me to write a post on how my chess work illustrates important statistical themes such as “regression to the mean” for #63, then a Thanksgiving post bringing both to 64. But the external part of my chess work, clear through to a release by FIDE yesterday which clarifies some things that may enable me to write a post on my experiences, and another project we will be able to mention soon (plus matters covered here including several papers), have kept me super-busy. Pip is now at 98, and the whole blog at 589 + 6 permanent pages.
Congratulations again, Dick!
For readers of this blog: Though it was hard to fit everything in the press release, the formal citation in this month’s SIGACT News due out soon also mentions the important contribution that Dick has made to TCS through this blog.
Ken: There is a way to clear up the “inconsistency”. Initially, the Knuth prize was set up for every 1.5 years with talks alternating between STOC and FOCS. It was switched to an annual prize after 2010, still alternating between STOC and FOCS. Conveniently, the n-th Knuth Prize is now given in year 2000+n.
Paul, thanks and great about the citation—I did preserve the distinction between citation and “release” in that line of the intro section, and used the “non-mention” just to be playful. The SIGACT Knuth Prize description page does still say “awarded every 1-1/2 years” so it should be updated. Dick did remark to me this morning before the post about the “14 in ’14” aspect, so we’re glad it is annual so that will continue :-).
congrats RJL on an award well deserved. was just poking around on knuths web site & thinking what a pity/ shame it is that he doesnt blog at all. 🙁
he writes many various blog-like opinions on his site but no comments. also he just had a new lecture “Let’s Not Dumb Down the History of Computer Science” and also “speaking informally about my experiences with SAT solving”. how interesting would those be?!? can someone get videos of these?
yes TCS foundations are turning out to be far, far harder than anyone imagined. was toying with idea of asking about “adjectives used by experts describing difficulties in complexity theory” on stackexchange but figure it would be quickly shot down. at least there are very candid writers such as yourself willing to be honest about the difficulties. they are truly the most honorable difficulties to have, some of the hardest ever encountered in science. (and should that be a coincidence given that it is indeed the “science of hardness”? that is not merely a comment entirely in jest….)
but still am optimistic and think some extremely revolutionary findings might be just around the corner. think that not very many people are truly working on the foundations & they arent nec engaged in a lot of teamwork. agree with you that more teamwork & multidisciplinary energy may be the key. think it is a truly formidable yet scalable barrier.
this blog is a real public service/ treasure & its truly amazing how much time you guys dedicate to it. esp appreciate your openness to “outsiders” 🙂
one other point. have long thought/ advocated that major progress could be achieved with more acceptance of empirical/ experimental approaches. they are already used very heavily in some areas such as SAT, but have noticed they also seem to be largely avoided elsewhere. there are probably many reasons for that but think that skepticism (possibly part of conventional wisdom) on their potential is not really warranted. another point, Michael Nielsen seems to have many great ideas for scientific advancment in his new book reinventing discovery but its still apparently (undeservably) low profile.
Congratulations to Dick Lipton for recognition deserved and honor well-earned!
(and please allow me too to express interest in “Let’s Not Dumb Down the History of Computer Science”)
And please sustain this fine web-log (with Ken Regan), which is an ongoing delight and inspiration to many (including me).
Congratulations!
Congratulation Dick. Too late, why not some years earlier.
Rafee Kamouna.
Congratulations Dick! I am quite happy with that you are being recognized by this year’s Knuth Prize. Also, I would like to thank you for being my advisor.
In true GLL style, let me say a few words about my experiences Dick. I guess this is the first time that Dick has been in the “receiving end” as far as this blog is concerned! As the ACM press release has mentioned, as has Ken and the Stackexchange and DBLP pages that he has linked to, Dick has made many fundamental contributions to diverse areas of Computer Science. The immense breadth of Dick’s ideas was always evident in my meetings with him. Most of the occasions that we met, there was a problem or two that Dick would be obsessing about. These problems varied from graph algorithms, structural complexity theory, algebra, cryptography, learning theory, game theory, spectral graph theory, randomized algorithms, number theory and on and on.
I was always amazed with the amount of information that Dick used to be able to recollect. He is a vast ocean of knowledge about theorems, results, proofs and proof techniques. Every meeting with him has been a learning experience for me. Another quality that is worth mentioning is his infectious childlike enthusiasm for any research problem, without any prejudice, regardless of the area, sub-area or the perceived “hotness” of the problem.
As an advisor, Dick would always be very generous with his suggestions and ideas, and would give unlimited freedom for his students to work. If being his student was an honor, it was a privilege to have been involved in this very blog. It was a pleasure, and indeed a learning experience, to proofread and comment on Dick’s posts before they appeared in public.
Once again, hearty congratulations to Dick!
Indeed and thanks, Subruk!
For very many people (including me), an essential component of “Planet Lipton” is that it is an utopian planet.
Example Positive elements aren’t easy to perceive Microsoft’s recent layoffs and lab-closure(s), but in drafting a recent comment for Scott Aaronson’s Shtetl Optimized weblog, it turned out that Dick’s (and Ken’s) comments provided the essential positive perspective.
Needless to say, Donald Knuth’s writings (both technical and non-technical) similarly have for many decades illuminated the most positive elements of our STEAM community.
The world’s creative engine of STEAM optimism requires continuous stoking; this is yet another reason why (as it seems to me) the sustained STEAM-stoking efforts of Don and Dick and Ken deserve all of our appreciation and thanks.
Long may the cheerful kindly solar system of Planet Lipton, Planet Regan, Planet Knuth, and Planet Gowers too, shine brightly in our skies!
Does this have anything to do with steampunk?
Short Answer No.
Broader Answer Re-integrating “Art” into “STEM” does touch upon the artistic themes that are associated to steampunk broadly conceived — e.g. the themes of Neil Stephenson’s Diamond Age.
In this regard, I have an essay-in-waiting regarding the ancient virtues of laetitia (gladfulness) and hilaritus (cheerfulness), that the Romans displayed prominently on their Imperial coinage, and whose central significance to reasoned moral life Spinoza emphasizes (rightly as it seems to me).
Needless to say, our modern world of derivatives, millisecond trading, and bitcoins — and the great edifice of efficient-market economic theory — has entirely divorced laetitia and hilaritus from the communal process of valuation.
Was this divorce a mistake? Fans of steampunk, LOTR, Harry Potter, Star Trek, and Spinoza certainly think so.
Academic economists (and complexity theorists) not so much!