Is MATH Ready for P=NP? Is Alexandra Fahrenthold Ready for P=NP?

(This post was inspired by Harry Lewis emailing me about his granddaughter.)

Harry Lewis's grand daughter Alexandra Fahrenthold (see both pictures) wants information

on how to claim the Millennial prize, so she will be ready.

This raises the question: How likely is it that Alexandra will resolve P vs NP (or perhaps some other Millennium problem if she wants to rebel against her grandfather)?

And more seriously:

1) Have we made progress on P vs NP? (I think not.)

(By we  I mean the community, not Harry and I or Harry and I and Alexandra,

for which the answer is a more definite NO.)

2) If not then why not?

3) How does this compare historically to other open problems in Math?

We will refer to progress made in solving an open problem, though that is a tricky notion since only after a problem is solved can you look back and say what was progress.  One might also count subcases (e.g., n=4 case of FLT) as progress even if they don't help lead to the final proof. I quote a letter from Harry Lewis to me upon reading a first draft of this post:

The one larger point I would suggest adding is to add my operational definition of progress: Progress is being made on a problem if, when the solution is published, it will cite work being published today. Of course that is “operational” only after the fact. Demillo Lipton Perlis at the end have a nice riff on this. The alchemists thought they were making progress on turning lead to gold but they weren’t, even though we know that was actually a solvable problem. Likewise jumping off of higher and higher buildings was not making progress toward heavier than air flight.

---------------------------------------------------------

1) Have we made progress on P vs NP?

a) I tell my students that we have made progress on ruling out certain techniques.

They laugh at that, at which point I decide to not tell them that my PhD thesis was about that sort of thing (oracles). I could say

Once you know what's not going to work you can concentrate one what is going to work.

But that sounds hollow since very few people are working on techniques that

might work (The Geometric Complexity Program, see here, is the only exception I know of.)

b) Are there any partial results? Ryan Williams showed that SAT (and also counting mod versions of it) cannot be done in time n^c and space n^{o(1)} where c is 2cos(2pi/7) (see here).  That is the only concrete lower bound on SAT that I know of.  Is it progress? Sam Buss and Ryan Williams later showed (see here) that, using current techniques, this cannot be improved. If that inspires new techniques that push it further, that would be great. So it is progress? Hard to know now. 

c) There are some circuit lower bounds. One can debate if this is progress.

It will be a much better informed debate once the problem is solved.

So I would say VERY LITTLE PROGRESS.

------------------------------------------------

2) If not then why not?

a) It's only been open for 50 years. A drop in the mathematical bucket.

Counterargument: 50 years of 20th and 21st century mathematics is A LOT.

b) Sociology: The academic computer science conference-model induces us to get out a paper in time for the next conference deadline, and not think deeply about a problem.  Carl Smith thought that P vs NP would be solved by the son of a member of the communist party in the USSR (when there was a USSR) who did not have the pressure to get tenure and grants and such. He may be right.

Counterargument: there are some (1) mavericks who buck the system, and (2) people like Carl's son-of-a-party-member who are allowed to think deeply for years.

c) It's just dang hard! That's the real question. Paul Erdos said of the Collatz Conjecture:

        Mathematics may not be ready for such problems.

Is that true of P vs NP as well?

----------------------------------

3) History and Philosophy.

(In college I once took the following four courses in one semester: History of Philosophy, Philosophy of History, Philosophy of Philosophy, History of History.)

Let's look at problems that were open and then solved:

a) The Three Greek Problems of Antiquity: Squaring the circle (given a circle, construct a square with the same area), doubling the cube (given a line that is the edge of cube, construct another line that is the edge of a cube with twice the volume), trisecting an angle (given an angle, construct two lines whose angle is 1/3 of the given angle), with a straightedge and compass. (When I first heard of this problem I wondered how knowing what direction was North would help trisect an angle.) Posed in roughly 400BC. Not clear what posed means in this context. Did they ask for a construction OR did they ask for EITHER a construction OR a proof that there wasn't one?

This might be the closest analogy to P vs NP: At the time the problem was stated

 MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS. 

It took lots of new math, a better notation, and a different way of looking at numbers, to show that they  could not be done: Pierre Wantzel--doubling the cube (1837),Pierre Wantzel--trisection (1837), Lindemann-Weierstrass--squaring the circle (1882).

NOTE: Some sources list a fourth problem: constructing every regular polygon. Pierre Watnzel proved, in 1837, that a regular n-gon is constructible iff n is the product of a power of 2 and distinct Fermat  primes. (Why isn't Wantzel better known?) 

b) Fermat's Last Theorem. Given its origin, not quite clear when it was posed but 1640's seems fair. This could not be solved when it was posed (On an episode of Dr. Who they claim that Fermat had a simple proof. Note that Dr. Who is fictional and their PhD (if they has one) is probably not in mathematics.) 

MATHEMATICS WAS NOT READY FOR SUCH PROBLEMS, 

but not as much as the three Greek problems. Very steady progress on it, see  here. One of the real milestone was connecting it to other problems in Math. And then Wiles proved it in the 1990's. While the solution was a surprise when it happened it was not that much of a surprise.

QUESTION: Is P vs NP more similar to Greek3 or to FLT? 

c) Peano Arithmetic (and similar systems) are incomplete. Hilbert's 2nd problem (1900) asked to show the axioms of PA were consistent. Godel (1931) showed this could not be done.  Moreover, there are TRUE statements about numbers that PA cannot prove. I think people mostly thought PA was complete so one of the innovations was to think it was incomplete.  

MATHEMATICS WAS READY FOR SUCH PROBLEMS 

but it took the boldness to think PA was incomplete to solve it.  The math needed was known when Hilbert posed the problem. But of course, how to put it together was still quite a challenge.

d) The Continuum Hypothesis, CH, is that there is no cardinality between N and R. Cantor in 1878 asked for a proof that CH was true. It was Hilbert's first problem in 1900.

When Hilbert posed this problem in 1900

MATHEMATICS WAS NOT QUITE  READY FOR SUCH PROBLEMS.

The math to solve it wasn't quite there, but wasn't so far off (of course, that's in hindsight). Godel's model L (1940) was brilliant, though Lowenhiem-Skolem had constructed models.  A model of set theory that was defined by levels was, I think, though of by Russell (though in a very diff way than L). When Cohen did a model where CH is false (1963) he invented forcing for Set Theory, though forcing had already been used in Recursion theory (The Kleene-Post construction of intermediary Turing degrees.)

e) Hilbert's tenth problem (1900): Find an algorithm that will, given a poly in many variables over Z, determine if it has a solution in Z.

MATHEMATICS WAS ALMOST READY FOR SUCH PROBLEMS.

I turns out that there is no such algorithm. Similar to CH: Once it was thought that it was unsolvable, the proof that it was unsolvable just took a few decades. However, it did need  the definition of computable to be pinned down.  Davis-Putnam-Robinson outlined what was needed in the 1950's,and Matiyasevich finished it in 1970.  While it required just the right combination of ideas, and lots of cleverness, the math needed was known.

CAVEAT: There are many restrictions of H10 that are still open. My favorite: is the following solvable: given k, does x^3 + y^3 + z^3 = k have a solution in Z? (See my blog post on this problem here.) For a survey of what is known about subcases see (1) my paper here, though it is has been argued that I am looking at the wrong subcases (see my blog post on this here), and (2) Bogdan Grechuk's paper here

CAVEAT: Matiyasevich has suggested that Hilbert really meant to ask about equations and solutions over  Q. That problem is still open. If it is unsolvable, that might be proven reasonably soon. If it is solvable, then

MATHEMATICS IS NOT READY FOR SUCH PROBLEMS.

f) The four color theorem. Posed in 1852 by Francis Guthrie, proven in 1976. Haken, Appel, and Koch (more on that last name later) did do some very impressive math to set the problem up, and the computer program to finish it off. When the problem was posed (1852) the computing power was not up to the task. So 

COMPUTER SCIENCE WAS NOT READY FOR SUCH PROBLEMS.

Could the ideas to set it up have been done earlier? Maybe, but not much earlier. The result is often attributed to Haken and Appel, but actually there are two papers, and Koch is an author on the second one. Note that (1) Robertson, Sanders, Seymour, Thomas had a simpler, though still computer proof (1996), and (2) Werner Gonthier formalized the proof inside the Coq proof assistant in 2005.

CAVEAT: An open problem that is hard to state precisely is to come up with a non-computer proof.

CAVEAT: There is a non-computer proof that every planar graph is 4.5-colorable, see my blog post in this here. (No, this is not a joke. If it was I would make if funnier and claim there is a non-computer proof that every planar graph is 4 + 1/e colorable.)

g) Poincare Conjecture. Conjectured in 1904 and solved in 2002. To bad---if it was solved in 2004 it would be exactly 100 years. There was some progress on this all along so I don't know which step was the hard one though probably they were all hard. This one is harder for me to speculate on. When it was solved and Darling wanted to know why it was worth $1,000,000 I told her that it says if something tastes and smells and feels like a sphere, its a sphere. She was unimpressed.  But back to our story:  in hindsight,

MATH WAS READY FOR SUCH PROBLEMS

 since there was steady progress. I think of NOT READY as meaning NO progress, NO plan.

h) The Erdos Distance Problem: Show that for any n points in the plane the number of distinct distances is Omega(n/\sqrt{log n}). Not quite solved, but a big milestone was Gutz and Katz proof of Omega(n/log n). For that result

MATH WAS READY FOR SUCH PROBLEMS

Steady progress:  see the Wikipedia entry here. What's of interest to us is that there was a barrier result of Omega(n^{8/9}) by Ruzsa (apparently unpublished) that said the techniques being used could not do better-- so people, in short order, found new techniques.  Here is hoping that happens with P vs NP.

--------------------------------------------------------------------------------

Let's look at problems that are open and unsolved.

a) Collatz Conjecture (also called the 3x+1 conjecture). I asked

Jeff Lagarias, who is an expert on the problem:

Is it true? When will it be resolved? He said Yes and Never.

I once heard there has been NO progress on this problem, though I later  heard that Terry Tao has made some progress. In any case, not much progress has been made. Maybe Erdos was right.

QUESTION: Why does my spell checker think that Collatz is not a word? 

b) Small Ramsey Numbers. I asked Stanislaw Radziszowski, who is an expert on Small Ramsey Numbers (he has a dynamic survey on small Ramsey numbers here) 

What is R(5)?  When will we know? He said 43 and Never.

Worse than being hard, I don't think any nice math has come out of trying to find R(5,5). Too bad. The coloring that gives the lower bound for R(4) and some (perhaps all) of the R(i,j) where i,j\le 4 can be derived from group theory. YEAH! But then connections to interesting math just... stopped. For now? Forever? Joel Spencer told me this is an example of the law of small numbers: patterns that hold for small numbers stop holding when the numbers get too big. (I've seen other things  called the law of small numbers as well.) 

MATH MAY NEVER BE READY FOR SUCH PROBLEMS 

If no interesting math comes out of the attempt to find the exact values of the Ramsey Numbers, then it is not a good problem. 

Note:  The conversations about Collatz and R(5) were within 10 minutes of each other. Depressing day!

c) The Twin Primes Conjecture. Sieve methods have been used to get partial result. YEAH! Yitang Zhang showed there exists infinite x such that x and x + 70million (something like that are prime. YEAH. Its been gotten down to x, x+246 and with various assumptions x,x+12 or x, x+6). YEAH! but Sieve methods are known to NOT be able to prove the  conjecture. Dang it!

DO NOT KNOW IF MATH IS READY FOR SUCH PROBLEMS.

I think people are kind of stuck here. Much like P vs NP, though at least they have some partial results. By contrast, with regard to P vs NP we don't even have that (unless you count Ryan's lower bound on SAT---maybe you do).

Note: I found that information here which seems to be an Encyclopedia Britannica  website. I would have thought that, with the web and Wikipedia, they would be out of business. Good for them to still be in business! 

d) I am not qualified to write about any of the Millennium prizes except P vs NP (am I even qualified for that?)  so I ask my readers to leave opinions (informed or not) about, for which of them, 

MATH IS NOT READY FOR SUCH PROBLEMS

One of the people who worked on the Riemann Hypothesis said: 

I do not recommend spending half your life on the Riemann Hypothesis. 

That raises a different question: When do you give up? (topic for a different blog post). 

e) I am also not qualified to write about the Hilbert Problems where are still unsolved. Note that some of them are not well enough defined  to ever be resolved (H6: Make Physics rigorous) and some are either solved or unsolved depending on who you ask (H4: Construct ALL metrics where lines are geodesics-- surely, he didn't mean ALL metrics. Probably right, but  stop calling me Shirley!) For a byte more about Hilbert's problems, including a few paragraphs on H4,  see my reviews of two books on them, here. Same as the last item- if you have an opinion (informed or not) about, for which of them that are though to be sort-of open, is math ready for them, leave a comment. 

CODA: Alexandra will be working on Collatz this summer!

Let's wish her luck!

A Young Person's Game?

When László Babai first announced his graph isomorphism in quasipolynomial time result, I wrote

We think of theory as a young person's game, most of the big breakthroughs coming from researchers early in their careers. Babai is 65, having just won the Knuth Prize for his lifetime work on interactive proofs, group algorithms and communication complexity. Babai uses his extensive knowledge of combinatorics and group theory to get his algorithm. No young researcher could have had the knowledge base or maturity to be able to put the pieces together the way that Babai did.

Babai's proof is an exceptional story, but it is exceptional. Most CS theorists have done their best work early in their career. I got myself into a twitter discussion on the topic. For me, I'm proud of the research I did through my forties, but I'll always be best known, research wise, for my work on interactive proofs around 1990. It would be hard to run a scientific study to determine cause and effect but here are some reasons, based on my own experiences, on why we don't see research dominated by the senior people in theory.

The field changes - Computation complexity has moved from a computational-based discipline to one now dominated by combinatorics, algebra and analysis. I'm not complaining, a field should evolve over time but it plays less to my strengths. It's hard to teach this old dog new tricks.

The fruit hanged lower - there were important problems with easier proofs available then not available now

Responsibilities - You have fewer as a PhD student, postdoc or assistant professor.

Family - becomes more of a focus.

Taking on new jobs - Many academics, though not all, take on administrative roles at their university or , or leave academics completely. 

The young people have the new ideas - And older people get settled in their ways

The thrill is gone or at least decays - Your first theorem, your first talk, your first conference paper gives you a level of excitement that's hard to match.

Existentialism - The realization that while computing has no doubt changed the world, my research, for the most part, hasn't.

Cognitive Decline - Probably the most controversial but for me I find it hard to focus on problems like I used to. Back in the day I prided myself on knowing all the proofs of my theorems, now I can't even remember the theorems.

Honestly there is just nothing wrong with taking on new roles, writing books, surveys and blogs, focusing on teaching and mentorship and service and leaving the great research to the next generation.

I have a book out on muffins (you prob already know that)

Lance: How come you haven't blogged on your muffin book? You've blogged about two books by Harry Lewis (see here and here) one book by the lesswrong community (see here), and you even did a mashup of a post by two different Scott A's (see here),  but not on your own work.

Bill: I thought I did a post on my muffin book.

Lance: No. You have blogged about the muffin problem, and sometimes you mention either the book or the problem in passing, but you haven't had a post that says

HEY, I wrote a book!

And this is all the more strange since you asked me to have the book on our blog page. 

Bill: (Searches blog with keyword muffin and finds no ref to muffin book). Well pierce my ears and call be drafty! I have not posted on the muffin book! Do you recall my thoughts on when to tell people you are working on a book?

Lance: No

Bill:  I had a college roommate who was an aspiring science fiction writer who told me there are two kinds of people: Those who talk about writing a book, and those who write a book. I have adapted this to:

Do not tell people you are writing a book until you are picking out the cover art.

Lance: I posted about my book when I hadn't even decided on the title. But your cover art is picked out (see here).  And, by the way, its very nice, though it makes me hungry. So I think you can begin talking about the book.

Bill: Indeed! I will!

------------------------------------------------------------------------------------

Hey I have a book! (See here to buy it on amazon.) 

Title: Mathematical Muffin Morsels: Nobody Wants a Small Piece

by Gasarch, Metz, Prinz, Smolyak

(The other authors were undergraduates when we wrote the book. Prinz and Smolyak are now grad students in CS, Metz is in Finance.) 

Origin: 

Martin Gardner wrote a Mathematics Recreational column for Scientific American for many years, starting in 1956 and ending in the early 1980s. For many STEM people of my generation (Using my fake birthday of Oct 1, 1960, I am 62 years old) Martin Gardner's columns were both an inspiration and an early exposure to mathematics. His columns also made the line between Mathematical Recreation and so-called serious mathematics thin or nonexistent. (See here for a review of Martin Gardner in the 21st century, a book about the kind of math Gardner wrote of. The book makes a mockery of the distinction between recreational and serious mathematics.) He passed away in 2010 at the age of 95.

There is a gathering in his honor that is hold roughly every 2 years, called Gathering For Gardner. (It was cancelled in Spring 2020 and Spring 2021 because of COVID- though its in Atlanta where the CDC is, so they could have had it as an experiment and told the CDC the results). You have to be invited to goto it. I got an invite for 2016 from my contact at World Scientific who published my previous book, Problems with a Point: Exploring Math and Computer Science co-authored with Clyde Kruskal  (I had two blogs on it, here and here, and you can buy it on amazon here.) I did three posts on G4G-2016 (here, here, and here).

Aside from seeing some great talks that I understood and liked, I also picked up a pamphlet titled:

The Julia Robinson Math Festival

A Sample of Mathematical Puzzles

Compiled By Nancy Blackman

One of the problems, credited to Alan Frank, was

How can you divide and distribute 5 muffins for 3 students so that everyone gets 5/3 and the smallest piece is as big as possible?

They had some other values for muffins and students as well. 

I solved the (5,3) problem and the other ones as well. That was fun. 

When I got home I began looking at the problem for m muffins and s students. I let f(m,s) be the biggest smallest piece possible for giving out m muffins to s students. I proved a general theorem, called the Floor-Ceiling theorem, that always gives an upper bound, FC(m,s) on f(m,s). I worked out formulas for 

f(m,1) (trivial), 

f(m,2) (trivial), 

f(m,3) (its always FC(m,3),

 f(m,4) (its always FC(m,4)).

While working on f(m,5) I found that  f(m,5) was always FC(m,5) EXCEPT for m=11. So what's up with f(11,5)?  

By the Floor Ceiling theorem f(11,5) \le 11/25. We (at that point several ugrads and HS students had joined the project)  were unable to find a protocol that would show f(11,5)\ge 11/25. Personally I thought there WAS such an protocol but perhaps it was more complicated than the ones we had found (We were finding them by hand using some easy linear algebra.) Perhaps a computer program was needed. We did find a protocol for f(11,5)\ge 13/30, which surely was not optimal. 

While on an Amtrak I began working out the following train of thought: The protocol for f(11,5)\le 11/25 MUST have 

(1) every muffin cut into two pieces,

(2) 3 students get 4 pieces, 

(3) 2 students get 5 pieces. 

While working on getting a protocol for f(11,5)\le 11/25 with these properties I found that... there could be no such protocol! Then by reworking what I did I found that f(11,5)\le 13/30. So it was done! and we had a new technique, which we call The Half Method. To see the full proof see my slides here

The story above is typical: We get f(m,k) for all 1\le k\le SOMETHING, we get stuck, and then we find ANOTHER technique to show upper bounds (which in this case are limits on how well we can do). This happened about 8 times depending on how you count.  After a while we realized that this could not just be an article, this was a book! World Scienfiic agreed to publish it, and its out now.

Misc Notes

1) I got a conference paper out of it, in the Fun with Algorithms Conference, with some of the co-authors on the book, and some other people. here is the conf paper.

2) Early on we realized that f(m,s) = (m/s)f(s,m) so we only had to look at the m>s case.

3) The fact that f(m,s) exists and is rational is not obvious, but is true. In fact, f(m,s) can be found by a mixed-int program. 

4) Late on in the process I found that there was a by-invite-only math newsgroup that had discussed the problem, and in fact was where Alan Frank first posted it. I obtained their materials and found that they had already shown f(m,s)=(m/s)f(s,m) and also that the answer is always rational and exists. Aside from that our results did not overlap.

5) Even later in the process Scott Huddleston emailed me (out of the blue) that he had a program that solved the muffin problem quickly. I was skeptical at first, but he did indeed have a whole new way to look at the problem and his code was very fast (I had Jacob Prinz, one of the co-authors on the book, recode it). Later Richard Chatwin (see here) seems to have proven that Scott's method always works. The approach of Scott and Richard is where to go if you want to do serious further research on Muffins. My book is where you want to go if you want to learn some easy and fun math (a HS student could read it). 

6) I co-authored a column with Scott H, Erik Metz, Jacob Prinz on Muffins, featuring his technique, in Lane's complexity column, here.

7) I had an REU student, Stephanie Warman, write a muffin package based on the book.

8) I gave a talk an invited talk on The Muffin Problem  at a Joint AMS-MAA meeting. 

9) I gave a talk at Gathering for Gardner 2018 on The Muffin Problem. 

10) I often give talks on it to groups of High School students.

11) When I teach Discrete Math Honors I talk about it and assign problems on it- it really is part of the course. As such its a good way to reinforce the pigeon hole principle. 

12) I contacted Alan Frank about my work. We arranged to meet at an MIT combinatorics seminar where I was to give a talk on muffins. He brought 11 muffins, with 1 cut (1/2,1/2), 2 cut (14/30,16/30),

and 8 cut (13/30,17/30) so that the 11 of us could each get 11/5 with smallest piece 13/30. 

13) Coda: 

Why did I keep working on this problem?  I kept working on it because I kept hitting barriers and (with co-authors) breaking them with new techniques that were interesting.  If early on a barrier was not breakable then I would have stopped. If (say) Floor-ceiling solved everything than I might have gotten a paper out of  this, but surely not a book.

Lesson for all of us: look around you! Its not clear what is going to inspire a project!

Lasting effect: I am reluctant to throw out old math magazines and pamphlets since you never know when one will lead to a book.

C++ is for Cookie and That's Good Enough for Me

Potbelly, a local sandwich chain, made me an offer I couldn't refuse: change my password and earn a free (and quite tasty) oatmeal chocolate chip cookie. A free cookie is a great motivator, and checking that this wasn't some clever phishing attack, changed my password and got my cookie. Not sure why Potbelly wanted me to change my password but happy to take their cookie.

Potbelly likely didn't make this offer to everyone so what if you want a cookie?

1. Use an app to get a cookie delivered.
2. Visit a specialty cookie store.
3. Go to your local supermarket and pick up a package of Chip's Ahoy.
4. Buy some pre-made cookie dough and put it in the oven.
5. Buy some cookie mix, add ingredients and bake.
6. Find a cookie recipe, buy the ingredients and get cooking
7. Get fresh ingredients direct from a farm stand
8. Grow and gather your own ingredients, ala Pancakes Pancakes

In machine learning we seem to be heading into a similar set of choices

1. Not even realize you are using machine learning, such as recommendations on Netflix or Facebook.
2. Using ML implicitly, like talking to Alexa
3. Using pre-trained ML through an app, like Google Translate
4. Using pre-trained ML through an API
5. Using a model like GPT-3 with an appropriate prompt
6. Use an easily trained model like Amazon Fraud Detector
7. An integrated machine learning environment like Sagemaker
8. Use pre-built ML tools like TensorFlow or PyTorch
9. Code up your own ML algorithms in C++
10. Build your own hardware and software

and probably missing a few options.

When you want cookies or learning, do you buy it prepackaged or do you roll your own? And when people offer it to you for free, how wary should you be?

How have computers changed society? Harry Lewis (with co-authors) have a book out on that.

 (Disclosure - Harry Lewis was my PhD advisor.)

It seems like just a few weeks ago I I blogged about a book of Harry Lewis's that was recently available (see here).  And now I am blogging about another one. Writing two books in two years seems hard! I can only think of one other computer scientist who has done that recently (see here and here).

In 2008 Abelson, Ledeen, and Lewis wrote 

Blown to Bits: Your Life, Liberty, and Happiness after the Digital Explosion

which I reviewed in SIGACT news, see here

Both computers and society have changed since 2008. Hence an update was needed. 

In 2021 Adelson, Ledeen, Lewis, and Seltzer wrote a second edition.

Should you buy the new version if you bought the old version? 

1) Not my problem- I got them both for free since I reviewed them. 

2) Not your problem- The second edition is available free-on-line here. Is that a link to some dark corner of the dark web? No, its the formal webpage about the book. So the book is available free-on-line legally, if you care (and even if you don't care). 

3) If you like paper, the book is on amazon. (If you don't like paper, the book is still on amazon). 

I reviewed it in SIGACT news. A non-paywalled link: here (is that link legal? I have no idea.) 

In this post I'll just mention two things that changed since the last book

1) Shared Music and pirating were an issue back in 2008.  It does not seem to be anymore since there is now a variety of services that seem to make pirating not worth it: itunes, streaming services, and some bands give it away for free and ask you to pay what its worth. Movies are still struggling with this issue. 

2) AI systems that reinforce existing bias is a new problem.

Being the Chair

If you have Netflix and interested in the academic world, I recommend The Chair, a six-episode dramatic series starring Sandra Oh as a new English department chair at a "lower tier ivy league university". The series takes many artistic liberties and compresses much in a short time period but gets much about academics right such as the tension between faculty and the administration with the chair caught in the middle, the need to create majors that attract students, faculty past their prime teaching the same courses in the same way for decades, faculty who get themselves in a hole and keep digging, alumni donors controlling academic decisions, pressure to build a diverse faculty, faculty feeling under appreciated and getting outside offers, and a wonderful exposition of how the field has changed over the past thirty years given to someone who had dropped out before finishing their PhD to take on a different career.

When I served as department chair at Georgia Tech, I dealt with most if not all of these issues above, though not at the same time. I had some challenges that today's English department doesn't face: how to handle enrollments that more than doubled while barely able to hire more faculty than were departing, not that I would trade in a second for the existential crisis that English departments are going through. 

When I left Georgia Tech after seven years, I had outlasted every other current chair in the Colleges of Computing, Science and Engineering. Not sure what this says about me or about Georgia Tech.

Being chair is the most challenging job in academia. The faculty technically report to you but you aren't their boss in any traditional sense--they came to academia because of the freedom to work on what they want and they won't give it up. It's virtually impossible to fire anyone with tenure. The joke goes that a chair needs two umbrellas, one to block stuff coming from the administration going to the faculty and the other to block the stuff from the faculty from going to the administration. Since I left it has gotten much uglier in the University System of Georgia which has no mask or vaccine mandates and glad I'm not the chair to deal with that.

This all sounds like I'm discouraging of becoming a department chair and it certainly isn't a job for anyone but it can be a very rewarding job. You can help shape the future of the department by the faculty you hire and the vision you set and create an environment that helps your faculty and students succeed. 

My academic lineage and more interesting facts that come out of it

 I got my PhD from Harvard in 1985 with advisor Harry Lewis

Harry Lewis got his PhD from Harvard in 1974 with advisor Burton Dreben (Dreben was in the Philosophy department and did logic). Burton Dreben never got a PhD (more on that later). So I thought my lineage stopped there. A while back I was in an email conversation with Harry and for some odd reason Galileo came up.

He then emailed me the following:

----------------

Did you know you were descended from Galileo, via Newton? See below. The data is from the Math Genealogy project (see here). As you know  Dreben had no PhD, but it would certainly be fair to call Quine his advisor anyway. And, in fact, the Math Geneology project lists Quine as Dreben's advisor. By starting with Dreben and clicking backwards I found the following:

In the list below everyone was advised (in some form) by the person below them.

William Gasarch, Harvard 1985

Harry Lewis, Harvard 1974

Burton Dreben, Harvard 1955

WVO Quine, Harvard 1932

AN Whitehead, Cambridge 1884

Edward John Routh, Cambridge 1857

William Hopkins, Cambridge 1830

Adam Sedgwick, Cambridge 1811

Thomas Jones, Cambridge 1782

Thomas Postlethwaite, Cambridge 1756

Stephen Whisson, Cambridge 1742

Walter Taylor, Cambridge 1723

Robert Smith, Cambridge 1715

Roger Coles, Cambridge 1706

Isaac Newton, Cambridge 1668

Isaac Barrow, Cambridge 1652

Vincenzo Viviani, Pisa 1642

Galileo Galilei, Pisa 1585

--------------------------------------

A few observations

1) Dreben was a philosophy professor at Harvard without a PhD. How? He was a Junior Fellow, which is for brilliant people, some of which were made professors without  the burden of going  through the PhD-getting ritual.  Andrew Gleason was a professor of Math at Harvard without a PhD-- also a junior fellow (he solved Hilbert's 5th problem, which surely helped). Tom Cheatham was a CS professor at Harvard who did not have a PhD but  was not a junior fellow. I do not know how he did that. Things are more formal now, and more people have PhD's, so I suspect it is much rarer to be a professor without a PhD.  Harvard still has the Junior Fellows Program, but even they have PhDs now. If someone solved P vs NP as an ugrad, I suspect they would be hired as a professor even though they do not have a PhD. That's one way for a theorist to get out of taking graduate systems courses. 

2) Note that Galileo and Vincenzo were in Pisa but then a long line of people from Cambridge. In those days schools hired their own. Is this good or bad? They know what they are getting, but you could have an old-boys-network blocking fresh new talent, and you may get stuck in your ways. Nowadays, at least in America, it is uncommon to stay at the same school as you got your PhD.

3) The shift from Pisa to Cambridge might be part of a more general phenomena--- the intellectual center for science shifting from Italy to England. What caused this? Amir Alexander, in his book Infinitesimals: How a dangerous mathematical idea shaped the modern world (see my review here ) speculates that the Catholic Church's rejection of Infinitesimals was the cause.  I suspect that letting non-scientists interfere with science was the cause (a lesson for us all).

4) Lance did a blog on his lineage here. He has Gauss and Euler as ancestors. 

5) To honor the myths about  my two most famous academic ancestors, Galileo and Newton,  I am going to travel to Italy and have Darling drop two apples of different weights off the leaning tower of Pisa and see if they hit my head at the same time.

Why Conferences?

An undergrad thesis from North Carolina State University tries to tackle the question as to why computer science has used conferences as its main and most prestigious publication venues. The author Elijah Bouma-Sims gives a synopsis with some interesting follow up conversation in this Twitter thread.

The upshot is that the conference culture grew organically early in computing and just took hold as the field grew. My personal non-scientific theory is that technology not available to earlier fields, namely jet airplanes, allowed CS to have national and international meetings that researchers could regularly attend. Before that conferences in more established fields like math were held either locally (AMS sectional meetings) or less often (ICM held every four years), traditions that continue to this day.

Covid has temporarily suspended fully on-site conferences, and new technologies allow us to have virtual meetings. It's still not clear what will be the new normal for conferences. I hope we get to the model where we have more virtual meetings and rarer in-person meetings that people make more of an effort to attend. Conferences focused on networking instead of publications.

The culture of conference publications has been slowly changing. Many subfields in CS, though not no much theory, have moved to a hybrid model where papers are submitted to a journal and those accepted are invited to be presented at a conference.

Conferences used to be the first place you would hear about new results but that's no longer the case. Papers posted on arXiv get noticed and Google Scholar doesn't distinguished citations to an arXiv paper differently from any other publication venue. 

Now you don't even need a presentation or a paper, just a promise of one. How many of you are excited about linear-size locally testable codes based on a talk announcement alone?

The New Jeopardy Champion is a `A CS grad student from a school in New Haven'

 As of Sept 17, Matt Amodio has won 23 straight games in a row on Jeopardy and won over $800,000 in regular play. The following website is not quite up to date, but its close: here. Of course, that website will change. 

1) They refer to him as A CS grad student from a school in New Haven. My first thought was probably Yale, but whatever it is, they should just say it. I looked it up and it is Yale. So why aren't they just saying A CS grad student from Yale?  If someone works for an airline company they do not tell you which airline- prob to avoid giving that airline free publicity. But I would think a school is different. And I remember (perhaps incorrectly) that they DO say what school someone teaches at or is a student at. 

(ADDED LATER: a colleague of mine who was on Jeop (he lost his only game) tells me that YES, you re NOT ALLOWED to say the company you work for. He was from Riverdale Park, MD which might make some people think there is a Univ of MD at Riverdale Park . He also told me that when he was on the show the following happened:  On One of the shows of the game before I  played, Alex was curious which LA area restaurant somebody worked at (to see if he had eaten there--- he hadn't), and sure enough, they edited the name of the restaurant out.)

2) Longest streak: Ken Jennings: 74. Also most money in reg play: roughly 2.5 Mill

    2nd longest: James Holzhauer: 32. Also  2nd most money in reg play: roughly 2.4 Mill

    3rd longest: Matt Amodio: 23. Also  3rd most money in reg play: roughly 0.8 Mill

3) I do not think Matt will move into second place on any of these categories. He bets big on the daily doubles and it has paid off but either (a) he will miss and it will lead to a loss, or (b) he will just not get the daily double and be against a very good opponent. Item (b) happened to James H- and the person who beat him did have a good enough win streak to be in the Tournament of Champions. I wonder if they try to stop a long streak by picking really good opponents. I also wonder if they can even tell who will be a really good opponent. 

4) Matt has played in front of (or will- counting tomorrow) six hosts: Robin Roberts, LeVar Burton, David Faber, Joe Buck, Mike Richards, and Mayim Bialik. Six is a record which I suspect won't be broken, except possibly by Matt himself if he also plays in front of Ken Jennings (the rest of 2021 will be Mayim B and Ken J as hosts, see here.

5) Matt works in AI. When he gets his PhD and is on the job market will his Jeopardy success help him, hurt him, or neither?  

6) James H and Matt A are both very good at calculating how much to bet. I think Ken J is not quite as good but still good. Generally the players on Jeop are not that good at that aspect. I had the chance to ask some a champions (not any of those three) why that was and she said that most people get into because of the trivia-aspect, not the betting aspect. I wonder if just as players now study lots of facts to prep, they will also learn how to bet better. 

7) Ken J as host is a bit odd in that, if he says (as Alex T did sometimes) That category looks hard I won't believe him. I also have this suspicion that when a contestant gets something wrong Ken might be thinking what a moron; however, (a) by all accounts Ken is a nice guy, and (b)  I might be projecting. 

Review of A Blog Book based on the Less Wrong Blog

There is a blog called lesswrong. Many people contribute to it (how many people must contribute to a website before it stops being called a blog and starts being called... Not sure what?). The theme is rationality. They (not sure who they are) have made a best-of collection from lesswrong which is named

A Map that Reflects the Territory (available here)

Actually, its not one book, but five mini-books. I quote the titles and paraphrase the first sentence of each:

Epistemology:  How we come to know the world.

Agency: The ability to take action in the world and control the future.

Coordination:  The ability of multiple agents to work together.

Curiosity: The desire to understand how the world works.

Alignment: The problem of aligning the thoughts and goals.

I have written a review of the the book. The book was my first exposure to the blog, except sometimes reading about the blog, probably on Scott's blog.

I am posting this to both complexity blog and to lesswrong, though with lesswrong I will have a different intro since they know lesswrong but might not know complextyblog. 

My review is here.

I would appreciate intelligent comments and suggestions, which I will use to improve the review.

The Death of Expertise

Four years ago I tried to catch up with deep learning and this summer I aimed to try to catch up again. Who would've thought 2017 is ancient history.

I watched the lectures in the latest MIT course, played with GPT-3 and Codex, read the new Stanford manifesto on what they call foundation models, models trained that can perform on a wide range of tasks instead of a single goal. We've seen machine learning solve protein folding, detect cancer from x-rays better than radiologists, not to mention effectively solving many of the traditional AI problems (language translation, voice and face recognition, game playing, etc.) Watching Codex generate computer code from plain English is a game changer. Far from perfect but this technology is in its infancy.

From what I can tell, the main technological advances focus on learning when we don't have labeled data such as new techniques to transfer knowledge to new domains and using generative models to provide more data to train ML algorithms.

The trend that worries us all is that deep learning algorithms in the long run seem to do better if we limit or eliminate previous human knowledge from the equation. The game playing algorithms now train from just the rules alone (or even just the outcomes). We do use some knowledge: words come in some linear order, faces have hierarchical features, but not much more than that. Human expertise can help as we start solving a problem, even just to know what good solutions look like, but then it often gets in the way.

When we longer use a skill we tend to lose it, like my ability to navigate from a good map. If we eliminate expertise we may find it very difficult to get it back.

There's a more personal issue--people spend their entire careers creating their expertise in some area, and that expertise is often a source of pride and a source of income. If someone comes along and tells you that expertise is no longer needed, or even worse irrelevant or that it gets in the way, you might feel protective, and under guise of our expertise tear down the learning algorithm. That attitude will just make us more irrelevant--better to use our expertise to guide the machine learning models to overcome their limitations. 

You can't stop progress, but you can shape it.

Guest Post on Solving (or trying to) Poly Diophantine Equations by Bogdan Grechuk

(Guest post by Bogdan Grechuk)

Motivated by Mathoverflow question here I have recently became interested in solving Polynomial Diophantine equations, that is, equations of the form

P(x₁,...,x_n)=0
for some polynomial P with integer coefficients. Because there are many such equations, I have decided to ask a computer to help me. Our conversation is presented here.

Highlights of the conversation: the height of a polynomial over Z in many variables is what you get when you make all of the coefficients positive and plug in x=2. For example, the height of

x³ - y⁴ + 5
is 2³ + 2⁴ + 5 = 8 + 16 + 5 = 29.

Note that, for all h, there are only a finite number of polynomials in many vars over Z with height h. With the help of my friend the computer we have looked at the equations with h=0,1,2,... and so on, and tried to  determine which ones have any integer solutions. As expected, the first equations were trivial, but at about h=22 we have started to meet quite interesting equations for which we needed help from  Mathoverflow to solve. The project is currently at h=29, with only one remaining open equation of this height.  Read the conversation with the computer, or my mathoverflow question

here or my paper:

here to find out more. I INVITE you to join me in this quest!

The hierarchy and GapP

There is a great but little-known theorem from the early 90's by Seinosuke Toda and Mitsunori Ogihara (buried as Lemma 2.3 in their paper) that shows the polynomial-time hierarchy is randomly low for Gap-P.

Let M be a non-deterministic polynomial-time machine. #M(x) is the number of accepting paths of M on x. #P is the set of functions f such that f(x) = #M(x) for an NP machine M. 

Gap-M(x) is the difference between the number of accepting and rejecting paths. Unlike #M(x), Gap-M(x) could be negative. Gap-P is the set of functions such that f(x)=Gap-M(x) for an NP machine M. Equivalently Gap-P is the difference of two #P functions. Gap-P inherits all the nice closure properties of #P while being closed under negation and subtraction.

Theorem (Toda-Ogihara): Let q be a polynomial and f be a function in Gap-P^PH. There is a function g in Gap-P and a polynomial p such that for all x, if you choose a binary string r randomly of length p(|x|), f(x) = g(x,r) with probability at least 1-2^-q(|x|).

In other words, with randomness the PH as an oracle of Gap-P disappears.

Let me show you how the proof works for a specific f in GapP^PH, namely the indicator function for SAT: f(φ) = 1 if φ is satisfiable and 0 otherwise.

Recall Valiant-Vazirani showed how to randomly reduce a formula φ to a set of formula ψ₁,…,ψ_k such that

1. If φ is not satisfiable then for all i, ψ_i will not be satisfiable
2. If φ is satisfiable then with high probability for some i, ψ_i will have exactly one satisfying assignment.

Picking k > 4|x|q(|x|) will reduce the error in (2) to under 2^-q(|x|). Let g(φ,r) use r to choose ψ₁,…,ψ_k and output the Gap-P function 1-∏(1-#ψ_i) using the closure properties of Gap-P where #ψ_i is the number of satisfying assignments to ψ_i.

• If φ is not satisfiable then for all i, #ψ_i=0 and g(φ,r) = 0.
• If φ is satisfiable then with high probability for some i, #ψ_i=1 and thus g(φ,r) = 1.

Note that if r is a bad random sequence and φ is satisfiable, g(φ,r) might be an exponentially large integer, positive or negative. It's right most of the time but when it's wrong it's terribly wrong.

Since we will soon be back in the classroom, how was Zoom? Anything you want to maintain?

UMCP will have all classes on campus this Fall. There is a Mask Mandate. All students and faculty have to get vaccinated unless they have a health or religious exception. 92% are vaccinated, which I interpret as people are NOT abusing the exceptions (though I still wish it was higher, and it may go higher). (ADED LATER- right after I posted this I got an email saying that UMCP is now up to 97%).  Those NOT vaccinated have to get tested - I think twice a week. 

Now that we are back in the live-classroom, here are some thoughts about teaching on zoom. 

I taught on zoom:

Spring 2020: The last half of both Ramsey Theory and Automata Theory(Reg, CFG,P,NP,Dec,Undec)

Fall 2021:  Cryptography 

Spring 2021: Honors Discrete Math and Automata theory

a) I taught in the usual time slot but I recorded the lecture so those who could not make it (more common during the pandemic) could still see it. Attendance was low, verbal interaction was low, but chat-interaction was very good. Looking into if we can do a chat in an in-person class. I was recording lectures before the pandemic and will keep doing so.

b) My exams were open-notes, open-book, open-web. That cuts down on ways they can cheat, though they can still phone-a-friend. Or ask their cat.  Unusual-but-correct answers can happen, as I discussed in this blog.

c) I gave my muffin talk a few times on zoom. In person it goes very well as my enthusiasm is contagious.  On Zoom that affect is dampened so the audience was more sedate.  I gave it as a special lecture to High School students and to my REU students. Note that it was NOT part of a class so the usual motivation to learn it to do the HW is gone. Hence its more important they be excited about it. 

d) In person I carefully make sure that I wear a funny T-shirt every day, and its a diff one, and usually a math one to (if possible) match the topic. On Zoom I did not bother, though I sometimes used wallpaper to match the topic. 

e) I had to make up slides for Aut theory and for some of Discrete Math. For Crypto I already had slides. I like the slides I made up and will use them in the future. But see next point. 

f) In Discrete Math I went  faster than usual- perhaps because its on slides, perhaps because there were less questions since it was on zoom, perhaps because Emily my  TA was so awesome that they had less questions. (She is very interested in education and did a guest post about the pandemic and education here.) As a result I actually learned and presented the proofs that (1) the e is irrational (my slides are here) and that Liouville numbers are transcendental (my slides are here). While I enjoyed learning those theorems and I think the students understood them on some level, I will slow down next time.

g) Ramsey Theory: It is impossible to teach the Poly VDW theorem on slides, so I had to omit that part of the course. 

h) Bottom Line: Did the students learn more? less? the same? My impression is that the students learned about the same, but really really didn't like it. And thats legit- that is NOT just students complaining. 

The Long Road

Guest blogger Varsha Dani tells us why it's never too late.

This week, I am starting as an Assistant Professor at RIT and I am super excited about it. What's the big deal, you are probably thinking. Don't lots of people get hired in tenure track positions every year? Sure. But the difference in my case is that I got my Ph.D. in 2008. 

Why didn't I look for a position right away? There were a number of reasons. I was burned out. I was going to have a baby. The job market was not particularly good that year. I would have had a two-body problem. And most importantly, I thought it was just going to be a short break. I thought that there was no rush...

What did I do in those intervening years? A lot of things. I spent a lot of time with my kids, including part home-schooling them for some time. I found some new interests, both in Math and CS and outside. I found new collaborators and did some research in new areas, just for fun. Sometimes I was funded for it through grants, but mostly I wasn't. I wrote a lot of Computer Science and some math materials for Brilliant.org. I organized math clubs at my kids' elementary and middle schools. I hiked. I wrote poetry. I never intended nearly 13 years to go by, but somehow they did.  At some point I remembered that I had meant to take a short break, not to give up on being an academic altogether. But by then it seemed too late. At the beginning of my meant-to-be-short hiatus, I used to jokingly refer to myself as a "scholar at large" but by the time a decade had gone by I had started to feel extremely isolated and being a scholar for its own sake was not something to joke about anymore.  Each year I rolled the job-search dice, but with each passing year it seemed more and more futile to do so, and more and more of an imposition to ask people to write recommendations for me. And then, out of the blue, last year, I found a whole community of independent researchers who, like me, were pursuing their scholarly interests despite not being employed to do so, and who felt unapologetically unembarrassed, even proud of it.  And, even more out of the blue, this year I got an offer. And now, this Fall, I am actually doing it. I am actually an academic! To be honest, I feel more than a little trepidation about it, mixed in with the excitement. 

So why am I telling you this? Partly to celebrate. Partly to publicly thank my spouse, who has been extremely supportive of all my decisions (and all my actions that were born of indecision) over many years. Partly to give a shout-out to the wonderful folks at the Ronin Institute who helped me remember that we do science (and computer science) because we love it, not because it pays the bills. Ironically, I believe I needed to be reminded of that before I could get a job! But mostly, I'm writing this to reach out to anyone out there who thinks that their decisions have led to a one-way street they no longer want to be on. It may be hard, and there are, of course, no guarantees, but you won't know whether you can turn around, unless you try. 

When Words Get Stretched Beyond Their Original meaning

STORY ONE:

 On a Jeopardy rerun with Alex Trebek the question (actually the answer, given the shows format) was (I paraphrase)

Who resigned his commision in the US Army Air Force in April 1941 after President Roosevelt publicly rebuked him for his views?

The answer (actually the question--Why does Jeopardy do this answer-question thing, drives me nuts!) was

Charles Lindbergh.

Alex Trebek then said  Charles Lindberg's views on WW II were not politically correct.

This really struck me since Politically correct means, to quote Wikipedia:

a term used to describe language, policies, or measures that are intended to avoid offense of disadvantage to members of particular groups in society. 

Wikipedia also adds that the term is generally used pejoratively with an implication that these policies are excessive or unwarranted. 

 But Alex Trebek is using the term to mean  incorrect or perhaps incorrect given what we know now or if you think history is written by the winners, then perhaps incorrect since Germany lost the war.  But my point is that I really don't think the term  politically incorrect  makes sense here.

STORY TWO

More recently I heard an anti-masker say

We should not let some woke school board take the right to not wear a mask away from parents and children.

Independent of if you are anti-mask-mandates or pro-mask-mandates, this seems like a strange use of the word  woke  which means, to paraphrase Wikipedia:

Having an awareness of racial prejudice, gender prejudice, sexual orientation prejudice, and the past and current discrimination they have and do cause. 

I've seen it both positively and negatively.

The anti-masker's using of the term seems odd in that mask wearing is not a woke issue. Perhaps he should have said 

We should not let some Nazi school board take the right to not wear a mask away from parents and children.

The term  Nazi while not actually correct, conveys that the school board is authoritarian. However, he really could not use the term that since he was was a neo-Nazi and proud of it. That raises a question: what pejorative  term can a Neo-Nazi use when they want to say someone is  Authoritarian? I ask non-rhetoically. 

But I am getting off topic here- my real point is that the word woke is being used to mean Authoritarian which is not even close to its original meaning. 

MY POINT

The above are examples of how a word in English may change its definition over time, which is not really news, but I found the examples interesting since I saw the origin of these words.

BILL, THIS IS A COMPLEXITY BLOG! SO TALK ABOUT COMPLEXITY. OR MATH!

In math do words change their meaning over time? Yes. Here are a few

Function: at one time `function' implicitly means a function that occurs in nature. So only continous and perhaps diff functions qualified. 

Sets: probably similar.

Efficient: At one time this was an informal notion (Joe Kruskal's paper on MST (see here) is an example of that), then it seemed to be P or perhaps BPP. For some its linear or O(n log n) with a small constant. Rather than say the notion changed, its more like it was never that well defined in the first place, and still isn't. 

Constructive: The many diff definitions of this word could be a blog post of its own. In fact, I thought it was, but I could not find it. I did find lots of blog posts that use the word constructive in diff ways. 

Elementary: Also has many definitions, though they are closer together than for Constructive. This one I did do a post on here

Trusting Scientists

 A tweet that made me think.

If you think you don't trust scientists, you're mistaken. You trust scientists in a million different ways every time you step on a plane, or for that matter turn on your tap or open a can of beans. The fact that you're unaware of this doesn't mean it's not so.

— Paul Graham (@paulg) July 26, 2021

The point here is subtle. We don't get on a plane because we "trust scientists", rather we do so because of the strong safety record of commercial aviation. I knew some physicists who won't get on a commuter plane because they worry about the science. Never stopped me.

It is science that we trust to tell us why planes fly, or the water is our tap is (mostly) safe and healthy. I'm not a big fan of beans but not because of the science. Of course I trust science that created the vaccines.

It's not just science, but solid engineering and lots and lots of testing. 

Science isn't always right or consistent. When I was a kid not that long ago, we had nine planets in this solar system, dinosaurs were killed off by climate change and homosexuality was a mental illness. Science is fluid, updating as we learn with new data, models and experimentation. Science is at its best when it doesn't trust itself.

Sometimes people say trust in science to reinforce their beliefs. I've seen smart people say "Trust in the science" about whether vaccinated people should wear masks with completely different conclusions.

I'm a scientist, should you trust me? Let me quote another Paul G. 

“There’s a slightly humorous stereotype about computational complexity that says what we often end up doing is taking a problem that is solved a lot of the time in practice and proving that it’s actually very difficult,” said Goldberg.

The quote comes from a recent Quanta Magazine article about Paul's recent work with John Fearnley, Alexandros Hollender and Rahul Savani on the hardness of gradient descent. Even many NP-complete problems these days can often be solved in practice.

Let's end with the quote attributed to statistician George Box, "All models are wrong, but some are useful". Science gives us ways to understand the world and we need to both trust in the science but know the limitations of what it has to say.

What are the most important 46 papers in Computer Science? Harry Lewis has a book about them!

 (Disclosure:  Harry Lewis was my PhD advisor. For a blog post on  disclosures and bias see my post on that topic here.)

Harry Lewis has a book out: Ideas that Created the Future: Classic Papers in Computer Science

He picked out the 46 (why 46? Why not 46?) classic papers in computer science and, for each one, has a short article saying why its important, and then has the paper itself, though perhaps shortened (leave out the boring parts) or in some cases he has an excerpt of a book (e.g., The Mythical Man Month which is why I blogged about that book recently here).

Harry Lewis has blogged about his book here where he points to my review which is in SIGACT News. 

OR you an use my link to my review here. 

The list of 46 papers had some constraints, so if you wonder why isn't X there it might have hit one of those constraints.

1) No paper past 1980 (he had to stop somewhere).

2) He preferred short readable papers to long or unreadable ones (don't we all!). Before thinking `Gee why isn't paper X in the book' go read paper X. 

3) Some papers cost to much to get permission to reprint. My review points to one such paper that I found 5 links to on the web. 

4) We don't need X papers on topic Y.

Of more interest is some papers that you had not heard of but we can now see are important.

For more thought, read my review!

For even more information, buy the book!

Recognizing Faces

I sometimes have trouble recognizing faces, matching faces to people I've interacted with in the past. It's not a disease like prosopagnosia, I can certainly tell the difference between faces and have no trouble with people I work with directly. But if I haven't seen someone in a while, I may not recognize them or confuse them for someone else. It's especially bad out of context, say running into a professor in my campus on the streets of Frankfurt. It's gotten worse with age but I've had challenges my whole life.

I have my coping mechanisms. I start a conversation to get enough clues to figure out who I'm talking to. I'll google an image before I'm supposed to meet someone I haven't seen in a while. Sometimes I'll just say "Remind me how to pronounce your name again". Sometimes I'll just say something embarrassing thinking the person I'm talking to is someone else.

Name tags are useful, if it isn't obvious you are looking at them. Zoom has been great--everyone's name is just there. I worry that 18 months of zoom meetings means I've lost much of my coping ability, much the way I can no longer navigate by maps the way I used to.

We have technological solutions but mostly unable to make use of them. Through the magic of machine learning, computers have gotten extremely good at recognizing faces. Nevertheless Google Googles actively prevented their one killer app, telling you who you were looking at, for privacy reasons. Perhaps they could limit it to people in your contacts with pictures you uploaded. It would only recognize people you already know.

I know I'm not alone, and I'm writing this post so others won't feel alone. And next time you see me and I look confused, remind me of your name.

Combing two posts: Blankface (Scott Aa) and Is Science Slowing Down? (Scott Al)

(I also posted this to the Less Wrong Website. At least I tried to- I don't quite know if or when it will appear there as its my first post there.) 

Some papers result from taking two papers and combining them. Perhaps nobody else had read both of them so you can say something new! Or (looking over this post) it may guide people to two really good papers, or in this case two really good posts. 

This blog will draw from two excellent blog posts.

Scott Aaronson  blogged on  his website Aug 2, 2021 about blankfaces, people who let stupid or undefined rules dictate what you can do  without apology (see his post for a better explanation). One example that struck me I quote

No, I never applied for that grant. I spend two hours struggling to log in to a web portal designed by the world's top blankfaces until I finally gave up in despair. 

Scott Alexander blogged  on LessWrong on Nov 26, 2018 about Is science slowing down? which answers with an emphatic yes. His point is science-per-researcher is much less than it used to be, and he has graphs and stats to prove it (see his post for the evidence and some speculation as to why this is) One of the reasons he gave struck me which I quote

Certain features of the modern academic system like undepaid PhD's, interminably long postdocs, endless grant writing drudgery, and clueless funders have lowered productivity. The 1930's academic system was ineed 25x more effective at getting researchers to actually do good research.

(A commenter reminded me that Scott Alexander himself dismisses this reason. I do not.) 

(I note that he gives other reasons as well, most notably for our field that the low hanging fruit is gone. Our lack of progress on P vs NP is likely that its a hard problem, rather than the reason above. Of course, if its solved tomorrow by an outsider without funding, I will happily be proven wrong.) 

Scott Alexander hits upon two types of blankfaces (without using the term).

Grant writing drudgery: the rules for how to submit get more and more detailed an onerous. This is  what Scott Aaronson was alluding to. There are other ways its drudgery as well. 

Clueless Funders: the people deciding who gets funded might not know the area (actually in my experience the grant I've reviews have been quite good and the problem is more not enough money to award all that are deserving.) 

SO I pose the following non-rhetorically as always

1) How big a factor is the slowing down of science that blankfaces get in the way?

2) What can we do about it?

Pole Vault Live Blogging

As I write this I'm watching the women's pole vault final in the Olympics. Of the 15 women who made the finals, only four remain after two heights.

To expand on my tweet, I find the pole vault the purest of the Olympic Sports. No electronic monitors and timers, no biased judges, no video review. No points deducted for bad form or failing to stick the landing. No disqualification for a false start or stepping over a line. Either you clear the bar without knocking it down, or you don't.

The high jump has similar properties, but just not as cool looking.

All four made the third height. Now onto 4.85 meters. An American, a Greek, a Brit and a Russian (sorry I meant member of the Russian Olympic Committee).

Back in the day, the TV coverage was rather limited. We'd only see the Americans and the medal winners with too much time spend on human interest backgrounds. Now in the streaming world I can watch every competitor. The good and the bad. Live as it happens.

The Russian Anzhelika Sidorova just cleared 4.85 on her first attempt. So did the Brit Holly Bradshaw and the American Katie Nageotte. The Greek Katerina Stefanidi missed her first attempt but decided to pass on the rest. All now go to 4.90 but Stefanidi only gets two attempts while the rest get three.

Stefanidi missed her first attempt at 4.90. She gets one attempt left.

Sidorova and Bradshaw fail to even reach the bar. Nageotte can't clear the bar.

Now the moment that means everything for Stefanidi. Her last attempt. Make it or the rest get the medals. Stefaidi fails to get a good plant and doesn't get into the air at all. Her Olympics are over.

Second attempt for the others. Sidorva and Bardshaw knock down the bar. Nageotte clears the bar, putting her in prime position. Go USA!

Imagine if we judged research papers this way. Either they get into a conference or they don't. Wait, that is they way they happen, although not always without biased judging.

Sidorova is passing on her last attempt at 4.90. Bradshaw goes for it but hits the bar. She has to settle for Bronze.

Bar is now at 4.95 meters. 

Sidorova gets only one attempt at 4.95. If she makes it, she takes the lead, if she misses, she gets the silver. 

Sidorova doesn't clear and the gold goes to the American Katie Nageotte! 

Just for excitement Nageotte is going for 5.01 meters, which would be her first over five meters in competition. In the men's pole vault, the Swede Armand Duplantis (great pole vault name!) easily won the gold. He moved the bar to 6.19 meters to break his own world record. Came all so close in his first attempt but failed to clear. 

Nageotte is just too excited winning the gold to focus enough to make a serious attempt at 5.01. Can't blame her.

Thus ends the best sport in the Olympics.

Do Four Colors Suffice?

(Guest Post by David Marcus)

Comment by Bill: Haken and Appel proved that all planar maps are 4-colorable. Or did they? David Marcus emailed me that its not quite true and I asked him to post on it, so here it is. The meta point is that math can be very subtle.

And now David Marcus's post:

Is the Four Color Map Theorem true?

It is commonly believed that the Four Color Map Theorem says that four colors suffice to color a planar map. While this is true for any map a non-mathematician would dream up, it is not true for maps a mathematician might dream up without some restriction on the regions that are allowed. This is shown in Hud Hudson's Four Colors Do Not Suffice which appeared in the American Math Monthly, Volume 110,  No. 5, May 2003, pages 417--423. 

Hudson's article is written in a very entertaining style. I recommend that you read it. He constructs a map consisting of six regions R1,...,R6.  Each region is bounded and path connected. There is a line segment B that is  in the boundary of all six regions.  So, six colors are needed, since all six regions share a common boundary. The construction is similar to the topologist's sine curve. For each i , the union of Ri and B is not path connected. Hudson also shows that for any n, there is a map that requires at least n colors.

Hudson thus disproves the following statement:

1)  Four colors are sufficient to color any map drawn in the plane or on a sphere so that no two regions with a common boundary line are colored with the same color.

Appel and Haken actually proved the following:

2) Four colors are sufficient to color any planar graph so that no two vertices connected by an edge are colored with the same color.

Covid Stats

A stat often quoted: About 97% of hospitalized coronavirus patients have not been vaccinated.  

People take this as proof that once vaccinated no worries. But I have so many challenges with this statistic.

• This statistic is down from 100% a year ago. Are vaccines working poorer now?
• There are likely correlations to those vaccinated and those who take precautions like mask wearing and social distancing, though I'm sure which way those correlations go.
• Those unvaccinated are more likely to be near others unvaccinated so more likely get infected and hospitalized.

Even though one shouldn't draw the conclusion from the statistic, that doesn't mean the conclusion is false. The gold standard are the double-blind vaccine trials which clearly showed the vaccines more efficient and safe. So get the vaccine, not that this blog post will convince those who have been making the conscious choice not to vaccinate to change their minds.

The other stat I found odd was that the life expectancy dropped 1.5 years in 2020. This doesn't mean on average we'll live 1.5 year less. Rather it means that someone who lives their whole life in 2020 conditions, widespread Covid without vaccines, would on average live 1.5 years less than someone who live their entire life in 2019 conditions pre-Covid.

Oddly enough if you made it to 2021 your life expectancy will probably increase (assuming you've been vaccinated). We made tremendous progress in understanding vaccine technology in 2020. Also people with conditions that could have limited their later life span were more likely to be fatal Covid victims, meaning those who are left would live longer.

I wish problems I have with computers really were my fault

 As you know, the website for out for a few days, as Lance explained here.

When I first could not get to the this blog  my thought was

OH, I must have changed some setting by accident. When Lance gets back (he was on vacation) he'll know how to fix it. Bad timing that it happened when he was gone, though prob not an accident- with him on vacation I was at the site more often and had more of a chance to screw things up. AND Lance will tell me what I did and I'll know to not do it again. And I will learn more about how this all works which will help me in the future!

When Lance got back we found out that NO Bill didn't do anything wrong. The blog site company  that we work with did an update and BLAH BLAH BLAH.  Reminds me of the theme behind the TV show Seinfeld: No Hugs, No Learning. At least no learning. I am not in the slightest more enlightened. 

Lance worked with them and YADA YADA YADA the problem is fixed, so I am very happy about that. 

On the one hand I wish it had been my fault so I would learn something.  On he other hand, if it was my fault would it have been as easy to fix? Would I really have learned something? 

When something does not work my protocol is

1) Turn the machine off and on again (e.g., log out and log in again). I want to say 

this works surprisingly often

but I doubt this surprises any of my readers, or is even news to them.

2) Spend at most 5 minutes trying to fix it myself . You will soon see that 5 minutes is a good choice for me.

3) Ask staff or Lance or Darling or my TA  (depending on the problem). 

4) They tell me to log off and log on again. When I tell them I already have they do something magical and it works again. I then ask them:

a) Could I have fixed this myself. 2/3 of the time the answer is no. They don't mean intellectually. They mean that I do not have access to what I need to fix it.

b) Did I do something wrong? I want to know so I won't do it again. about 99/100 times the answer is that I did nothing wrong (I don't recall that last time that I did).

Given a and b, I think 5 minutes is all the time I want to spend to try to fix it myself. 

Technical Difficulties

After returning from vacation last weekend (hello North Dakota--my 49th state visited), all sorts of odd problems arose. This blog stopped working, a P v NP paper was published on the ACM Transactions of Computing website and my personal emails were getting marked as spam. All is better, I hope.

Years ago I donated the URL computationalcomplexity.org to the Computational Complexity Conference, coincidentally held this past week, with the condition that I could continue to use the "blog" subdomain for this blog. Organizations continue but the people in them change, and when the website was "upgraded" on Saturday the pointers to make this blog work were left out. Thanks to Ashwin Nayak for getting it all straightened out and we're back online.

For the ToCT paper, a paper claiming to reduce 3-SAT to 2-SAT, and thus show P = NP, was originally rejected by the journal but a "disposition field" got inadvertently set to accept and wasn't caught until it showed up online. Editor-in-Chief Ryan O'Donnell quickly got on the case and ACM has removed the paper. P v NP remains as open as ever.

Fixing the email required me to learn far more about SPFs than I ever wanted to know.

By the way if anyone in Idaho wants to invite me to give a talk, I might be interested.

Political Intersections: Trump honors Antifa member who was shot dead by police

 1) Trump and other reps have said the following about the Jan 6 event at various times:

a) The Jan 6 event was freedom fighters who were fighting the noble fight to overturn a fraudulent election. Rah Rah!

b) The Jan 6 event was a peaceful protest to overturn a fraudulent election. 

c) The Jan 6 event was democrats trying to make republicans look bad.

d) The Jan 6 event was Antifa. (See here)

e) Ashli Babbitt (a protestor who was shot by police at the Jan 6 event) should have been honored by flying the flag at half-mast (see here) 

If we take the intersection of d and e we find that Trump wants to honor a member of Antifa who was shot by police. 

To be fair, Trump is entitled to change his mind. But I wonder- did he ever really think it was Antifa or was that a talking point? If he really thought so then  when did he change his mind? I ask non rhetorically---  NOT a `gotcha question'

(NOTE: I wrote this post a while back. Since then Trump and some other republicans are tending towards the Freedom Fighters narrative.) 

2) Vaccines:

a) Some people think that the vaccines are bad to take. I suspect they would give some (incorrect) health reasons, while the real reason may be political. (One reason is that the vaccine make you magnetic. That sounds awesome! Others think that there is a microchip in the vaccine so that Bill Gates can track our movements. Gee, Mark Zuckerberg can already do that. Some thing it will rewrite our DNA. A bio major I know  tells me that such people are confusing messenger RNA with DNA. Great- we can now have a nice conversation and point out where they are wrong.) 

b) Some people think we should NOT give vaccines to poor countries that need them, or to people in prison,  since Americans should have priority. (NOTE- from a purely health-viewpoint this is not correct since a pandemic does not respect boundaries- if there is an outbreak in a diff country or in a prison it will affect people not in those countries and not in prison.) 

Are there people who believe a and b? I ask non-rhetorically. 

I am not surprised when people hold contradictory thoughts in their heads, but these two cases just struck me as particularly strange. Not sure why.

 

Would you take this bet (Part 2) ?

 Recall from my last post (here)

I offer you the following bet: 

I will flip a coin.

If  HEADS you get 1 dollar and we end there.

If TAILS I flip again

If  HEADS you get 2 dollars and we end there.

If  TAILS I flip again

If HEADS you get 4 dollars and we end there.

If TAILS I flip again

The expected value is infinity.

Would you pay $1000 to play this game?

Everyone who responded said NO. Most gave reasons similar to what I have below. 

This is called The St Petersburg Paradox. Not sure it's a paradox, but it is odd. The concrete question of would you pay $1000 to play might be a paradox since most people would say NO even though the expected value is infinity.  See here for more background.

Shapley (see here) gives a good reason why you would not  pay $1000 to play the game, and also how much you should pay to play the game (spoiler alert: not much). I will summarize his argument and then add to it. 

1) Shapley's argument: Lets say the game goes for 40 rounds. Then you are owed 2^{40} dollars. 

The amount of money in the world is, according to this article around 1.2 quadrillion dollars  which is roughly 2^{40} dollars. 

So the expected value calculation has to be capped at (say) 40 rounds. This means you expect to get 20 dollars! So pay 19 to play. 

2) My angle which is very similar: at what point is more money not going to change your life at all? For me it is way less than 2^{40} dollars. Hence I would not pay 1000. Or even 20. 

Exercise: If you think the game will go at most R rounds and you only wand D dollars, how much should you pay to play? You can also juggle more parameters - the bias of the coin, how much they pay out when you win. 

Does Shapley's discussions  resolve the paradox? It depends on what you consider paradoxical. If the paradox is that people would NOT pay 1000 even though the expected value is infinity, then Shapley  resolves the paradox  by contrasting the real world to the math world. 

Would you take this bet (Part 1) ?

 I am going to present a well known paradox (I didn't know it until last week, but the source I read said it was well known) and ask your opinion in this post, and reveal my thoughts in my next post.

I don't want you to go to the web and find out about it, I want your natural thoughts. Of course I can't stop you, but note that I did not give the name of the paradox. 

Here it is:

I offer you the following bet: 

I will flip a coin.

If  HEADS you get 1 dollar and we end there.

If TAILS I flip again

If  HEADS you get 2 dollars and we end there.

If  TAILS I flip again

If HEADS you get 4 dollars and we end there.

If TAILS I flip again

etc. 

1) Expected value: 

Prob of getting 1 dollar is 1/2

Prob of getting 2 dollars is 1/2^2

Prob of getting 2^2 dollars is 1/2^3

etc

Hence the Expected Value is 

1/2 + 1/2 + 1/2 + ... = INFINITY

QUESTION: Would you pay $1000 to play the game?

Leave your answer in the comments and you may say whatever you want as well,

but I request you don't give the name of the paradox if you know it. 

Intersecting Classes

If you have two complexity classes that have complete sets, the intersection might not, for example NP ∩ co-NP. The world of total-function classes acts differently.

Christos Papadimitriou and others defined a number of classes based on finding solutions to problems where solutions are known to exists for some combinatorial reason. While TFNP, the set of all such problems, might not have complete sets, all the other classes are defined basically based on the complete search problem for the class, such as PLS, finding a local minimum. If you have two such classes A and B with complete search problems A and B define the search problem D as 

D(x,y): Find a solution to either A(x) or B(y)

D is complete for the intersection of A and B: First the problem D is in A since you can reduce the problem of finding a solution to either A or B to finding a solution to A. Likewise D is in B.

Suppose you have a problem Z in A∩B. Then since Z is in A and A is complete for A, finding a solution to Z(u) reduces a finding a solution of A(x) where x is easily computed from u. Likewise Z(u) reduces to finding a solution of B(y). So whatever solution D(x,y) gives you, it allows you to find a solution to Z(u). Thus D is complete for A∩B.

Some people nerd out to helicopters on mars. I nerd out to the complexity of complete sets. 

I learned about complete sets of intersections of total function classes from the talk by one of last week's STOC best paper awardees, The Complexity of Gradient Descent by John Fearnley, Paul W. Goldberg, Alexandros Hollender and Rahul Savani. The part above was well known but the paper goes much further.

Consider PPAD famously with Nash Equilibrium as a complete problem and PLS. PPAD ∩ PLS has complete sets by the argument above. But we can go further.

The class CLS is a variation of PLS where you find a local minimum in a continuous domain under some Lipschitz conditions and is known to sit in the intersection of PPAD and PLS. Fearnley et al. look at finding a minimum using gradient descent (the main tool for deep learning), and showing not only is it CLS-compete but complete for PPAD ∩ PLS. As a consequence CLS = PPAD ∩ PLS. Pretty cool stuff.