Sunday, January 23, 2022

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. 


  1. > A scary thought: most results in math, once published,
    > are never looked at again. So there could be errors in
    > the math literature.

    If you don't use the result, then not much harm. If you use the result, maybe you should check the proof!

    1. In an ideal world one would check the proofs of all theorems one uses in a proof. In the real world this could be difficult. Hence I do wonder if some big result will end up not having a correct proof. Or even incorrect!

    2. I confess to sometimes using a theorem without checking the proof.

    3. @DM: Very relevant topic! If my recollections serve me well, Dudley made you disprove one of his published theorems via counterexample!
      So, you witnessed the phenomenon of flawed published proofs first hand.

    4. Dudley checked all his proofs, and (when he was my advisor) all my proofs. But, even Dudley sometimes made a mistake. Dudley already knew that his proof of that theorem was wrong, but didn't have a proof that the theorem (as stated) was false.

  2. There are definitely lots of errors in the math literature. There are many MathOverflow questions on this topic; e.g.,

    Voevodsky got interested in formal proofs in part because of wrong proofs that he himself had published.

    In other cases, a theorem is announced as proved, but the proof has yet to appear, even after many years. In some cases, later researchers have built on those theorems, despite the lack of proofs.

  3. @TC: Good points! Voevodsky is indeed a very interesting story,
    and figure in this space.
    The DLP paper that Bill refers to in (2) highlights some other
    stories that have equally surprised me. Well-written gem!

    The Easter Egg in the DLP paper is the spelling of Norbert Wiener as "Norbert Weiner"; I wonder what feedback this oversight generated.
    Then again CACM has not surprised me, my eyes have come across
    quite a few hiccups that the editors/reviewers should have spotted. (Who was the editor/reviewer for this piece back then ...).