Happy 1,000th Post and 75th Birthday, Dick

From Rich DeMillo

Richard Lipton founded this blog 1,000 posts ago. He was not quite as young as in the photo. This blog is almost 13 years old but measures time by the count of posts. Time itself occurs only between posts. Unlike what we said here about counting birthdays, we are counting “1,000 posts ago” correctly—because the blog was created before the first post with the pages one can click on above.

Today we—including many from the community—also salute Dick’s 75th birthday.

The birthday was last September 6. A year ago, I thought the anniversaries could be made to coincide, but the time between posts flowed heavily. Much as a ship captain’s personal attributes become vested in the ship, I felt the birthday could best be hailed at the blog milestone. In this we take after the Queen of England. Elizabeth Windsor was born on April 21 (1926), but follows the centuries-old royal custom of celebrating the birthday in late spring.

It has been my great pleasure to know Dick for 35 years in-person and several years before that through his papers. His STOC 1980 paper with Rich DeMillo on the possible independence of P versus NP influenced me to focus on systems of logic as a graduate student. We talked most at STACS 1994 in Caen, France, and this led to a paper with four others in the next STACS. I gave an invited talk at Dick’s 2008 birthday celebration workshop—of which more below—and this began our closer association the next year. Dick and the blog are a fount of ideas, and if I say I wish I had time to develop them all, the answer is that our readers are always freely welcome to do so.

The Elevator Workshop

It is also my delight to have a slate of volunteer speakers for a mini-workshop this coming Monday (Martin Luther King Day, January 17) starting at 4pm Eastern Time (US). It will have the theme “Open Problems”—what else?—actually there is “else” as some of the brief talks will be personal notes or nuggets of work that influenced careers. It is open to the public—all readers are invited to attend on Monday via the following Zoom link. Update: things worked fine, and I have removed the link…

…except to note that the passcode I made was 111317. I intended the passcode to be the three primes that multiply to 1,001, thinking of what comes next, but those three multiply to 2,431—way far ahead, but see Lance Fortnow’s comment below. There is no “Waiting Room” and no restriction on when to come or go.

Here are speakers who have volunteered so far—alphabetical except those in overseas time zones beginning with India will go first:

• Subruk Kalyanasundaram

• Ravi Kannan

• Gil Kalai

• Joel Ouaknine

• Harry Buhrman

• Jin-Yi Cai

• Zvi Galil

• Bill Gasarch

• Mitsunori Ogihara

• Rafail Ostrovsky

• Atri Rudra

• Santosh Vempala

• Michael Wehar

• Ryan Williams

And possibly a few more. Among the open problems, some may be “Favorite Problems” and some “Formative Problems.” The latter means ones that can shape the field during the coming decade. They should be both important and pliable. The latter word is a pun: it means flexible, but we also mean something a beginning researcher can ply into a dissertation and early career. Computational complexity has many problems that seem to have become rigid, but its sideways growth shows pliable ones are out there.

One of this blog’s first posts in February, 2009, was on conveying the key idea to solve a problem in the time of an elevator pitch. The same goes for the time to state a good problem. The talks, including pauses and time for questions, will aim to fit within an hour, or 90 minutes at most.

Some Well-Wishes

I am also thankful to have the following well-wishes thus far from around the community, including several more fellow bloggers.

• Scott Aaronson: Happy birthday Dick! Your results have been an inspiration to me, from DeMillo-Lipton in 1979 on the independence of P vs NP to self-testing of the permanent (which played a central role in my work on BosonSampling). I hear some of your students, like Avi Wigderson, have done OK stuff as well. I look forward to checking your blog for many years to come!

• Andrew Appel: I have Massive Memories of the decade and a half that we overlapped at Princeton, in which you were one of my mentors, explaining to me the ways of the world. When I arrived there from from my PhD it seemed like all the really senior professors (you among them) were celebrating their 40th birthdays. Very best wishes for your 75th.

• Boaz Barak: Congratulations to GLL for its 1,000th post and to Dick for his 75th birthday! Dick has done so much for computer science, including many works that have become part of our canon and shaped our “conventional wisdom.” And then with GLL both Ken and Dick have managed to inject fun and humanity into our technical field and also question some of that conventional wisdom itself. Looking forward to the next 1,000 posts!

• Paul Beame: Double congratulations, Dick! and congratulations to Ken, too. Through GLL you have helped foster a closer sense of community in our field. Your thought-provoking and informative posts and depth of engagement are inspirational.

• Avrim Blum: Very happy 75th birthday, Dick! We are fortunate to have you in our field!

• Harry Buhrman: Congratulations to Dick on his birthday and edition 1,000 of this blog. For me it is also the 42nd birthday of the beautiful Karp-Lipton theorem which is one of my favourite theorems. Its quantum variants are still very relevant and are currently of importance in the quantum computing community.

• Jin-Yi Cai: My most sincere well wishes to Dick’s 75th birthday! You have been an inspiration to so many of us over many decades! And warm congratulations to your successful 1,000th post! Your blog GLL, now with Ken, has become a most important landmark in our community. (And will speak, as above.)

• Rich DeMillo—see below.

• David Dobkin—see below.

• David Eppstein: Happy birthday, and congratulations on the 1,000th post! I always look forward to your posts, both for their clear explanations of difficult topics and for the way you lighten them up with the biographical parts. May you have many more excellent birthdays and posts.

• Ron Fagin: I have always enjoyed the Gödel’s Lost Letter blog. In fact, I view it as an important part of my computer science experience! Congratulations, Dick and Ken, on the 1,000th post!

• Lance Fortnow: Congrats to Dick and Ken for their millenary post. Learned much about chess, leprechauns, and even some theory. Best wishes for the next 1,000. BTW, Bill Gasarch and I are at 2895 posts so you have some catching up to do.

• Merrick Furst: Dick, it’s been an incredible pleasure to work with you and play with you and be allies with you since we first met and became fast friends in the late 70’s. What a long, strange, wonderfully complex trip it’s been. Wishing you all the best and hope to find a way to see you sometime soon.

• Bill Gasarch—will speak, as above.

• Gil Kalai—will speak, as above.

• Subruk Kalyanasundaram: I am delighted to see GLL complete 1,000 posts! Since its inception in February 2009, GLL has created and continues to exist in its own unique space. After putting up a handful of posts, Dick sent a few of us students an understated email that went something like “started a new blog. see if you like it.” At that time, I had no idea that Dick could keep it going for 1,000 posts. I was actively involved in proofreading posts in the first couple of years, but am still a regular reader. It was a privilege to see the posts a day or two before the rest of the world. GLL has been such a successful and popular blog, and wishing many many more exciting posts!

• Richard Karp: Dear Dick, It has been my good fortune to be your friend and collaborate with you over many years, especially during your Berkeley period. Gödel’s Last Letter has been a major source of information and insight for me, consistently demonstrating your virtuosity and the depth of your knowledge. Congratulations also to Kathryn for her support of your efforts, and to Ken for his fruitful partnership with you.

• Andrea LaPaugh: Dick, congratulations and the best of wishes as you celebrate your 1,000th GLL post and your 75th birthday! The great energy, insight and joy you bring to computational theory has been an inspiration to me and many others. May you enjoy your passion for theory, and life, for many years to come. (And more below.)

• Jonathan Lenchner: Congratulations on the 1,000th posting to the GLL blog—an incredible go-to reference for the computational complexity community! It has been great to reconnect with Ken, who I first met through chess, over logic. Sending belated well wishes also to Dick on the occasion of his 75th birthday!

• Harry Lewis: Dick—Thank you for being the guy who always made TCS fun! There is no one who better exemplifies the principle that irreverence is key to the creative process. You have always had the gift of showing how seriously you took the questions of the field by taking their canonical answers so lightly. Your milestone sounds better in French, so I’ll paraphrase: Happy sixty-somethingth! And may you be forever young.

• Daniel Lopresti: Dick, I want to wish you a happy (belated) 75th birthday. Your deep and broad insights have had a tremendous impact on me and many of our colleagues in the field of computer science over the years. With warm regards, Dan Lopresti.

• Danupon Nanongkai: About a decade ago, I had the privilege to learn about many exciting problems and insights from many meetings with Dick while I was his PhD student. That was when the Gödel’s Lost Letter blog started, and I am grateful that I can continue to learn by reading this blog. Congratulations on the 1,000th post and Dick’s 75th birthday!

• Mitsunori Ogihara—will speak, as above.

• Rafail Ostrovsky: My warmest congratulations to Dick and Kathryn on Dick’s birthday wishing Dick many more equally productive and healthy years to come and enjoy. GLL is a truly an inspiration to us all—big thank you to Dick and Ken for an amazing and always inspiring content.

• Joel Ouaknine: Thanks for the many many inspirational and insightful posts! I’ve learned more computer science and mathematics on GLL than in any other single source I can think of!

• Vijaya Ramachandran: As one of the Dick’s earlier Ph.D. students (graduating in 1983), I would like to offer Dick my best wishes for a very happy 75th birthday, and for many more years to come.

• Atri Rudra: I have always been and continue to be amazed by the frequency of posts on GLL especially given the mathematical depth of the exposition, which somehow still manages to be accessible to a wide audience. Here’s wishing to many more years of GLL posts being prolific!

• Terence Tao: Happy 1,000th post Dick! I very much appreciate the personal and inclusive style of mathematical storytelling that you bring to the mathematical blogging community. Look forward to the next 1,000.

• Santosh Vempala: My best wishes to Dick and many thanks to Dick and Ken for a 1,000 interesting posts! Here’s to the next 1,000.

• Suresh Venkatasubramanian: On the internet, last week is like 2 years ago. Or so it feels that way. While some of us are frantically trying to tweet our papers and TikTok our talks, it’s a testimonial to persistence and steadiness that GLL has reached its 1,000th blog post (although I would subscribe to a TikTok live feed of Ken and Dick composing their latest post). GLL is an oasis of depth and substance in the desert of social media, and I for one am glad it’s going strong.

• Avi Wigderson: I had the good fortune to be Dick Lipton’s PhD student in the years 1980-83. Being with a researcher so knowledgeable, curious, original and passionate in these formative years has shaped my own research path. Happy 75th, Dick, and many happy returns!

• Ryan Williams—will speak, as above.

• Virginia Vassilevska Williams: Happy 1,000th post, Dick! Your blog posts are always so fun to read, highly informative and polished, a treasured gift to our community. Thank you for working on them all this time. I’m looking forward to many more!

More may be added, and our readers are welcome to add more in the comments.

Some Words From Princeton—and Yale

Andrea LaPaugh recently retired after being a full professor since 1995 and serving as head of one of Princeton’s six residential colleges for some of that time. She has some further words from that perspective going back to the beginning of her 38 years at Princeton.

Dick was a major force in the development of the CS department at Princeton. His work was instrumental in the creation of the department as separate from Electrical Engineering, in recruiting faculty to grow the department, and in acquiring resources. He arrived in 1980 and immediately recruited David Dobkin as a full professor and me as an assistant professor. He continued to have major involvement in recruiting, not only in theoretical computer science, but across the CS disciplines. He was never chair, but worked first with Bruce Arden, chair of the Department of Electrical Engineering and Computer Science, and then with Bob Sedgewick, the first chair of the Department of Computer Science (after Dick recruited him) to implement a vision of a strong and well-rounded CS department. Of course Dick was not alone in this mission. David Dobkin in particular was an important partner. But from my perspective, Dick was the spark.

David Dobkin, also writing from Princeton, where he was Dean of the Faculty from 2003 to 2014, goes back a few years further still to Yale:

In 1973 when I arrived at Yale as a new faculty member with a fresh PhD, Dick Lipton was the person in the next office who had arrived perhaps a week earlier. He came by to introduce himself. After a bit of formalities, we began to discuss research problems and he asked me about NP-complete problems which were all the rage at the time. The only problem I knew about was the knapsack problem and so I described it.

This led to a discussion about integer programming (which neither of us had a good handle on) and then to a discussion about determining in which region of a subdivision of -space (by a set of hyperplanes) a new point was in. Here again, neither Dick nor I had much background and so we invented things as we went. I had this idea that we could understand things with visual help and so we took one of my moving boxes as our universe and the back of some tablets as planes and began to simulate how regions would be determined in 3d.

From this work emerged our first paper together which was presented at STOC ’74. This on planar subdivision searching opened up a field and led to a long and enjoyable collaboration that followed.

So, congratulations Dick on having escaped the world of cardboard planes in a moving box and headed on to a remarkable career in the field.

More Words From Georgia Tech

Rich DeMillo sent the following from summer sunshine and open water:

The last time I missed Dick’s birthday was 2008. In 2007, Dan Boneh, Merrick Furst, Santosh Vempala, and I sent the following 60th birthday symposium invitation to twenty of Lipton’s closest friends and collaborators:

The Lipton-60 Symposium was finally held in April 2008. It was less the retrospective I had imagined than a mile marker in a career that continued to accelerate in unexpected ways. A few years later, he was elected to the American Academy of Arts and Sciences. A few months after that, he was announced as winner of the 2014 Knuth Prize. Even more memorable was the other thing that draws us together here today: the launch in 2009 of the GLL blog that he now writes with Ken.

I have long since strayed from the mainstream of theory and algorithms, but most of the work we did together has found its way into GLL essays that illuminate in startling new ways material I thought I understood thoroughly. Our paper on the nature of proof that now appears in Harry Lewis’s collection of 46 of the most important (in his view) papers in computer science made its first appearance on the blog in 2009 and has been a recurring character in the “GLL universe” ever since. Our probabilistic algorithm for polynomial zero testing also entered GLL in 2009. For years I harbored vague resentment that Jack Schwartz was often cited in the Schwartz-Zippel Lemma for a result that Dick and I had published two years before in 1979, but the exposition in GLL, Ken’s subsequent commentary, and years later, a reader’s comment showing that Daniel Erickson’s 1974 Caltech dissertation had scooped us all, laid that to rest.

We both had a fascination with the idea of algorithm correctness—incorrectness, actually—that turned into entire fields in software engineering and cryptography. Those were documented in an “Un-Birthday” post a year ago:

Rich and I started our work together over four decades ago. A central theme of our work was correctness. We were concerned That programs might not work as planned. At the time it was not obvious that this was a major theme of our joint work. But looking back now I can see that it was.

Also recently, I managed to coax Dick into the fraught waters of election security. I stood back to watch how flustered researchers would respond to his (brilliant but unworkable) reconstructions of what it means to vote in a public election.

I have been delaying my plans to remove myself from day-to-day management duties to found a new department of cybersecurity at Georgia Tech, and I have missed Dick at my side since his retirement. There was always the possibility when Dick was in the room that someone’s long-held (but wrong) assumption would fall apart under a trademarked but understated Lipton assault. Michael Rabin (who also contributed to the Lipton-60 symposium) was fond of telling Dick on such occasions, “You are a very dangerous person.”

With this intimate gathering on January 17 to commemorate GLL 1,000 and Dick Lipton’s 75th Birthday, Ken Regan has slyly kept alive the tradition of meetings that take place months after the anniversary of Dick’s birth. Times are different. Virtual meetings have replaced the casual travel and camaraderie of 2008. I cannot attend in any form on January 17 since I am at present on a ship bound for the Drake Passage and Patagonia, and I will lose Internet connectivity soon. I hope that explanation excuses this longer-than-asked-for expression of affection and admiration for Dick, my friend and collaborator for nearly 50 years.

Open Problems

A meta open-problem: Which was the most pliable problem at the time this blog was founded? The Unique Games conjecture strikes us as a perfect example, but you readers may have other examples from then and now.

[fixed product 11*13*17, added more greetings and speakers, removed workshop link afterward; Dobkin not LaPaugh was Dean of the Faculty]