Personal Reflections on Dick Lipton in honor of his 1000th blog/75th bday.

 Is it an irony that Lipton's 1000th post and 75th bday are close together? No. Its a coincidence. People use irony/paradox/coincidence interchangeably. Hearing people make that mistake makes me literally want to strangle them. 

The community celebrated this milestone by having  talks on zoom in Lipton's honor. The  blog post by Ken Regan that announced the event and has a list of speakers is here. The talks were recorded so they should be available soon. YEAH KEN for organizing the event! We may one day be celebrating his 2000th blog post/Xth bday. 

I will celebrate this milestone by writing on how Lipton and his work have inspired and enlightened me. 

1) My talk at the Lipton zoom-day-of-talks was on the Chandra-Furst-Lipton (1983)  paper (see here) that sparked my interest in Ramsey Theory, lead to a paper I wrote that improved their upper and lower bounds, and lead to an educational open problem that I posted on this blog, that was answered. There is still more to do.  An expanded version of the slide talk I gave on the zoom-day is here. (Their paper also got me interested in Communication complexity.) 

2) I read the De Millo-Lipton-Perlis (1979) paper (see here) my first year in graduate school and found it very enlightening. NOT about program verification, which I did not know much about, but about how mathematics really works.  As an ugrad I was very much into THEOREM-PROOF-THEOREM-PROOF as the basis for truth. This is wrongheaded for two reasons (1) I did not see the value of intuition, and (2) I did not realize that the PROOF is not the END of the story, but the BEGINNING of a process of checking it- many people over time have to check a result. DLP woke me up to point (2) and (to a lesser extend) point (1). A scary thought: most results in math, once published, are never looked at again. So their could be errors in the math literature. However, the important results DO get looked at quite carefully. Even so, I worry that an important result will depend on one that has not been looked at much...Anyway, a link to a  blog post about a symposium about DLP is here.

3) The Karp-Lipton theorem is:  if SAT has poly sized circuits than PH collapses (see here), It connects uniform and non-uniform complexity.  This impressed me but also made me thing about IF-THEN statements. In this case something we don't think is true implies something else we don't think is true. So--- do we know something? Yes! The result has been used to get results like 

                                                   If GI is NPC then PH collapses.

This is evidence that GI is not NPC. 

4) Lipton originally blogged by himself and a blog book came out of that. I reviewed it in this column. Later it became the  Lipton-Regan blog, which also gave rise to a book, which I reviewed   here.  Both of these books inspired my blog book. This is a shout-out to BOTH Lipton AND Regan.

5) Lipton either thinks P=NP or pretends to since he wants people to NOT all think the same thing. Perhaps someone will prove P NE NP while trying to prove P=NP. Like in The Hitchhiker's Guide to the Galaxy where they say that to fly, you throw yourself on the ground and miss. I took Lipton's advice in another context: While trying to prove that there IS a protocol for 11 muffins, 5 students where everyone gets 11/5 and the smallest piece is 11/25, I wrote down what such a protocol  would have to satisfy (I was sincerely trying to find such a protocol) and ended up proving that you could not do better than 13/30 (for which I already had a protocol). Reminds me of a quote attributed to Erdos: when trying to prove X, spend half your time trying to prove X and half trying to prove NOT(X).

6) Lipton had a blog post (probably also a paper someplace) about using Ramsey Theory as the basis for a proof system (see here).  That inspired me to propose a potential randomized n^{log n) algorithm for the CLIQUE-GAP problem (see here). The comments showed why the idea could not work-- no surprise as my idea would have lead to NP contained in RTIME(n^{log n}). Still, it was fun to think about and I learned things in the effort.