Complexity Year in Review 2020

For the result of the year we go to all the way back to the "before times".

MIP*=RE by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright and Henry Yuen

A follow up to last year's runner up NEEXP in MIP*, the new paper shows how to prove everything computable and beyond to a polytime verifier with two provers who cannot communicate but share entangled quantum bits. The result had a bit of a scare but fixed up this fall.

Honorary mention goes to beating the Christofides-Serdyukov approximation for traveling salesman by Anna R. Karlin, Nathan Klein and Shayan Oveis Gharan. Nathan got his start in Bill's REU program.

Of course when we think back at 2020 it won't be the theorems but the pandemic, a divisive election and racial reckoning. The word of the year for academia is "virtual", virtual teaching, virtual research collaborations, virtual talks, virtual conferences, virtual panels and virtual job visits. For the most part the the pandemic hasn't really created new trends but accelerated trends already in place. Given the far lower costs in terms of time, money and the environment, how much of "virtual" will remain post-corona?

Bill's published a new book on muffin problems, his second book in two years. I started a new College of Computing. 

We remember Lars Arge, Ed Clarke, John Conway, Richard Dudley, Stanley Eisenstat, Ron Graham, Richard Guy, Katherine Johnson, Vaughn Jones, James Randi, Arianna Rosenbluth, Joy Thomas, Robin Thomas, Alex Trebek, Boris Tsirelson and Paul Young. 

Thanks to our guest posters Gorjan Alagic, Andrew Childs, Tom Goldstein, Daniel Gottsman, Clyde Kruskal and Jon Katz, Antoine Amarilli, Thomas Colcombet, Hugo Férée and Thomas Schwentick, Steve Butler, Varsha Dani, Evangelos Georgiadis and Emily Kaplitz.

In 2021 we will likely see the end of the pandemic and most definitely see the 50th anniversary of P versus NP. Hope for a successful and healthy year for all. 

Slowest Sorting Algorithms

Radu Gigore tweeted "People are obsessed with finding the best algorithms. What about the worst?" So here's a Christmas gift that keeps giving, the slowest of sorting algorithms. 

Before you read on, try to think of the slowest sorting algorithm. No fair spinning its wheels, sleeping or doing unrelated tasks. It should always make progress towards sorting. 

Here are some examples, in particular bogosort that generates all permutations until it finds a sorted one. Takes n! time on average.

But we can do much worse. The following redicusort algorithm I got from Stuart Kurtz back in the 90's.

Generate all permutations and then sort those permutations. The sort of the original permutation will be first on the list.

The running time depends on the sorting algorithm you use after generating the permutations.

If you use bubblesort you get a (n!)² time algorithm.

If you use bogosort you get a (n!)! bound.

What if you just call redicusort recursively? The algorithm will never end. If you want to guarantee termination you need to bound the depth of the recursion. Choose something like an Ackermann function to get a sorting algorithm that always makes progress but not primitively recursive. In general you can get a sorting algorithm that takes longer than any fixed computable function.

Dr Jill Biden

(I was helped on this post by Gorjan Alagic, Andrew Childs,  Tom Goldstein, Daniel Gottsman, Clyde Kruskal,  Jon Katz. I emailed them for their thoughts on the issue and some of those thoughts are embedded in the post. ) 

The First First Lady to have a college degree was Lucy Hayes (Rutherford B Hayes was Prez 1876-1880). Nickname: Lemonade Lucy since she did not serve alcohol. 

Trivia: who was the last first lady to not have a college degree? I'll answer that one at the end of this post. 

The First First Lady to keep her day job was Abigail Fillmore who was a teacher. (Millard Fillmore was Prez in 1850-1852. He became prez  after Zachary Taylor died in office) . 

In recent times it is  uncommon for a first lady to have a day job. So much so that it was notable when Elizabeth Dole said that if her husband (Bob Dole) won in 1996 she would keep her job at the Red Cross. 

For other first lady firsts  see here.

Jill Biden is the First First Lady to have a PhD. (ADDED LATER- one of the comments pointed out that she has an Ed. D, Doctor of Education.)   She says she will keep her day job as a professor.  Four other First ladies had advanced degrees: Pat Nixon (MS in Education), Laura Bush (MS in Library Science), Hillary Clinton (Law degree), Michelle Obama (Law degree). If I missed any, let me know. 

The WSJ had an op-ed  that said Jill Biden should not call herself `Dr'.  Inspired by that, here are thoughts on the use of the word `Dr'

1) At the 1986 Structures Conference (now Complexity Conference ) Lane Hemachandra (now Lane Hemaspaandra) gave a talk. He had just gotten his PhD a few weeks ago, so he was introduced as `DOCTOR Lane Hemchandra' Gee, most of the talks were by people with PhD's but were not introduced as such.

2) Most people I know within academia do not call themselves Dr since it sounds pretentious. However, speaking in public about an issue one might want to use `Dr' to signal that you...know stuff. However, it would be odd for a PhD in (say) linguistics to claim he knows a lot about (say) politics. It has been said: an Intellectual is someone who is an expert in one field and pontificates in another field. 

3) Does the general public think of DOCTOR as Medical Doctor? Probably yes. There are some exceptions: Dr. Martin Luther King and Dr. Henry Kissinger. Also, I think it is  more common in Psychology, pharmacy, education, and counseling to call yourself `Doctor'  

4) The article also criticized her PhD (in education, about community colleges) as `useless' . If that's the reason to not call her doctor than I shudder to think what the WSJ would think of degrees in, say, set theory with an emphasis on Large Cardinals. GEE, you can't call yourself  DOCTOR since your degree is on Ramsey Cardinals. OH, now they found an application, so now you CAN call yourself DOCTOR. OH, the application is to extending the Canonical Ramsey Theory from Polish spaces  to meta- compact  cardinals, so we can't call you DOCTOR after all. Do we really want to go down this path? 

5) I ask all of the following non-rhetorically:  Did the author read her PhD thesis? Is he qualified to judge it? Did he (as one should do) look at her entire body of work to judge her? What point is he trying to make anyway? 

6) Should Dr. Who call themselves a doctor? Are they  a medical doctor? PhD? If so, in what? Is `Who' part of their name? For other TV and movie tropes about the use of the word doctor, see here.

7) I avoid saying I am a doctor since people will then ask me about the medical condition.

I avoid saying I am a computer scientist since people will then ask me how to help them with their Facebook privacy settings. 

I avoid saying I am a mathematician since people will ask me to help their daughter with her trigonometry. 

8) The answer to my trivia question: The last first lady to not have a college degree: Melania Trump. She went to college for a year and then left. The one before her was Barbara Bush who also went for a year and then left. 

ADDED LATER: Many supervillians who don't have a PhD or an MD call themselves `Doctor', see here. Why no outrage about this? Because (1) they are fictional, and (2) imagine the scenario: Not only does Dr. Doom want to take over the world, he also doesn't even have a PhD or an MD!

ADDED LATER: Where does Dr. Pepper fit into this? 

Optiland

Many of you have heard of Russell Impagliazzo's five worlds from his 1995 classic A personal view of average-case complexity In short 

• Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. 
• Heuristica: NP problems are hard in the worst case but easy on average.
• Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. 
• Minicrypt: One-way functions exist but we do not have public-key cryptography.
• Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.

Impagliazzo's world has an explicit "you can't have your cake and eat it too", either you can solve NP-hard problems on average, or have cryptography but not both (neither is possible). That's the mathematical world of P v NP. 

The reality is looking more and more like Optiland, where we can solve difficult NP problems and still have cryptography thanks to vast improvements in machine learning and optimization on faster computers with specialized hardware.

Back in 2004 I gave my guess of the world of P = NP

Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.

Today you can take your smartphone, unlock it by having the phone scan your face, and ask it a question by talking and often get a reasonable answer, or have your question translated into a different language. You get alerts on your phone for weather and earthquakes, with far better predictions than we would have though possible a dozen years ago.

We have computed the shortest traveling-salesman tour through nearly 50K UK pubs. AlphaFold can simulate protein folding with an accuracy nearly as good as what we get with real-world experiments. You can view GPT-3 as generating a form of a universal prior. Even beyond P = NP, we have self-trained computers easily besting humans in Chess, Go and Poker.

Meanwhile these techniques have done little to break cryptographic functions. Plenty of cybersecurity attacks but rarely by breaking the cryptography. 

Not all is rosy--there is still much more we could do positively if P = NP  and we are already seeing some of the negative effects of learning such as loss of privacy. Nevertheless we are heading to a de facto best of both worlds when complexity theory tells us those worlds are incompatible. 

Quarterly Th. Wksp `at' Northwestern, and thoughts inspired by it

 On the Northwestern CS Theory Group there is a set of Quarterly Theory Workshops. There is one coming up on Dec 17-18, 2020, called the Junior Theorists Workshop. Take a look and possibly go to it! Because it is virtual you do not need to plan that much ahead- though they do want you to register. 

1) I notice broadly two kinds of meetings:

Based on WHO will be there, e.g., JUNIOR theorists

Based on TOPIC: e.g., there was a meeting on ALGORITHMIC FAIRNESS.

2) These types of meetings (NY Theory day is another) are, I believe, intended to be for people that are local (more on that later). But because the meeting will be on zoom, geography is no longer an impediment for either the attendees or the speakers. 

3) Before covid there was some talk of  `Gee, flying off to STOC, FOCS, other conferences is bad for the environment, what to do about that?'. With that in mind, here is a history which might not be true but makes a point:

In an earlier era FOCS/STOC were attended by mostly Americans and ICALP was attended by mostly Europeans.  I do not think there was any policy of discrimination on admissions, but it was more like Americans just did not submit to ICALP as much, nor Europeans  to FOCS/STOC. But over time when these conferences got to be considered prestigious people would routinely submit to either one depending on timing. If your paper was done in time for Conf X deadline, that's where you submit. If it does not get in then  you edit it some, perhaps add some new results, and submit to Conf Y. 

So one solution to the air-travel-global-Warming   problem of conferences is go back to a time (which may not have ever existed) where it was just understood that you go to LOCAL conferences. Math does this, but it helps that their regional conferences are not  prestigious. But even they don't quite get it right: the joint AMS-MAA meeting alternates coasts. One year when it was in California they invited me to be a guest speaker (on the Muffin Problem). The following year it was in Baltimore. Note that I live in Maryland, so perhaps they should have waited a year. 

How to encourage people to submit locally. I DO NOT want to have a rule or a diff standard for those who don't. As such... I have no idea. 

4)  Are virtual conferences a good idea? This is a hot topic now so I won't dwell on it, just to say that there is still something about being there IN PERSON, meeting people, serendipity that makes live confs better.

However, to have it at the same time be virtual and recorded will be VERY HELPFL to those who can't afford to go for whatever reason. 

And of course there is the whole issue of if we should have prestigious conferences, which I won't get into now. Or later. That's more Lance's issue (he thinks no). 

Shuffling Around

In the fall of 1983 as a junior at Cornell I took CS 481, Introduction to the Theory of Computing, from Juris Hartmanis. Needless to say this was the course that changed my life and led me down a path that would have me teach a variation of this course myself more than twenty times.

For some reason one of the final exam questions is still stuck in my head.

Let the permutation of a language L be the set of strings x such that there is a string y in L which is a permutation of the letters in x. For example perm({01},{001})={01,10,001,010,100}. 

Are regular languages closed under permutations?

There's a short and easy answer that's not so easy to find. Just in that P v NP spirit a Hartmanis test question should have. Give it a try before you read more.

If you ask Chegg you end up with 

And for $15 you can get the answer. Back in 1983 we called that cheating.

The hint only works if there are regular languages whose permutations are not context free. Which is true in general but oddly enough the permutation of every context-free language over a two-letter alphabet is context free. The proof uses Parikh's theorem which implies that the permutation of any context-free language is the permutation of a regular language (over any alphabet size).

Some other fun permutation questions:

• Show that NP is closed under permutations.
• Show that P is closed under permutations if and only if E = NE.
• What about NL and L?

Go ahead and chegg on those. 

In 1974 Planarity was O(V) time and could do 900 node graphs in 12 seconds! Fast then...

In 1974  Hopcroft and Tarjan showed that Planarity is in polynomial time. That is an understatement- they actually have an O(V) algorithm which one can actually code up. See their paper here.

It has the curious line:

An Algol implementation of the algorithm successfully tested graphs with as many as 900 vertices in less than 12 seconds.

900 nodes in 12 second was fast then but it slow now. 

1) How would their algorithm do on todays machines? How does that compare to what Moore's law (for time) would have predicted? Can this help us determine an x such that Moore's law stopped working at year x. I've  heard various candidates for x including the notion that the death of Moore's law has been greatly exaggerated. Moore himself is still alive, at the age of 91. 

2) Are there better algorithms now? Nothing can beat O(V); however, is there an algorithm  with a better constant? 

3) Is there a modern implementation of it (or perhaps even an old implementation run on a modern machine)? If so, how fast does it run on 900 nodes? 9000 nodes? 90,000 nodes? 900,000 nodes? Not sure where to stop.

4) The people in the real world who really need to solve this problem fast: (a) do they exist, and (b) if they do exist then what do they use? 

Chess is Back

Back in 2005, I wrote a post titled Chess and Poker. Not really comparing the two but noting that Chess had lost its mojo while poker had high-stakes prime time tournaments. The inspiration was an NYT Op-Ed that started "CHESS in America is having a crisis". I suggested that computers getting better than humans may have reduced interest in the game. 

Now chess is booming again, due to all of us being stuck at home and the Netflix limited series The Queen's Gambit (highly recommended). 

The fictional show takes place in the 1960's when interest in chess in the US started to pick up due to Bobby Fischer's exploits and well before computers played a decent game. Fischer isn't mentioned in the Netflix series, the main character Beth Harmon sort of plays his role. The games themselves, created by Gary Kasparov and others, are even a joy to watch. Check out this analysis of the final game (spoiler warning). 

The New York Times started a chess column in 1962 and ran its last column in 2014, though that might be saying more about the state of newspapers than the state of chess.

What about the computers? They have just gotten so good and with AlphaZero mastering the game with just machine learning on top of the rules of chess, it's not even fun to watch computer versus computer anymore. Now we're back to watching humans and getting back into the games ourselves.

Computers have opened the door to cheating. Complexity theorist Ken Regan has a side gig reviewing games to determine if a player punching above their weight secretly used a computer algorithm. 

Microsoft just announced chess programs that play as a human at various levels of strength. I suppose someone could use a program like this to cheat in a way that even Ken couldn't detect. But mostly it would be like Googling in pub trivia--just takes the fun out of the game.

James Randi, Magicians-Author-Skeptic, passed away at the age of 92

James The Amazing Randi died on October 20, 2020, at the age of 92. He is survived by

his husband Jose Alvarez.  His Wikipedia page is here

 

A few Randi Points:

0) Wikipedia lists his careers as Magician, Author, Skeptic. I didn't know that skeptic was a career.

1) Randi debunked many paranormal claims, though he did not like the term debunker. He preferred investigator.

2) Martin Gardner and James Randi founded the

Committee for Scientific Investigation of Claims of the Paranormal.

which publishes

The Skeptical Inquirer: see here  

3) The internet is both a place where unchecked claims of paranormal activity (and more dangerous lies) can grow faster than in an earlier time, but also a place where magazines like The Skeptical Inquirer, and fact-checking websites, can help check the unchecked claims. What is winning? I leave that as an exercise for the reader. 

4) I suspect most (all?) people reading this blog do not believe in astrology, UFO's, ESP, or other crank theories. Hence I was surprised to read that Alan Turing thought the evidence for  ESP was overwhelming. This was mentioned in passing in his paper on The Turing Test (called there The Imitation Game) as something the Turing Test will have to account for. I've tried to find out why he believed this, without success. Some websites mentioned that belief in the paranormal was more... normal in those days. One suggested that after the counter-intuitive theories of quantum mechanics and relatively were out there, other counter-intuitive theories took hold, like ESP.  Even so, what was the evidence he was referring to?

5) Claims that  I was abducted by a UFO or I saw a UFO have decreased since people now have cell phones so ALWAYS have a way to take pictures. Also rumors like (I had heard this one)

There is an alternative ending to the movie BLAH which made is way to a few DVDs by mistake.

are no longer made since IF true you could EASILY produce evidence of such (post to you tube or elsewhere).

6) The term skeptic just means someone who doubts something, and is not necc a positive things.

I am a skeptic when it comes go Global Warming

being one example.

Randi largely debunked things that were obviously false and not-political. (That the very existence of Global Warming is political is  appalling. At some future point the question of whether or not we ever got to the moon will be political: Something done by big government that worked is impossible, hence it did not happen. See Scott's Blog on disbelief that we ever went to the moon here. And people like Randi will need to debunk the notion that the moon landing was faked.) 

7) Back to Turing- There is a large diff between believing in ESP and believing in astrology.

For ESP Turing mentioned overwhelming evidence.  While he was WRONG, he did see the need to HAVE evidence. And note that ESP CAN be tested and found to NOT be true. Also note that it is plausible (though I really doubt it) that some humans somehow have some level of ESP. Astrology has NO redeeming value or hope whatsoever. (I am reminded that in Martin Gardner's book Fads and Fallacies in the name of science he noted that most people would say things like `YES, I liked your debunking of A, but you are wrong about B--- B is for real!')

UFO's: I do not believe that aliens have come here and abducted people or left crop circles or anything of the sort. The intelligent question of  is there intelligent life in the universe  is quite another matter.

7) When I saw magicians as a kid (1960's) I knew that it was all tricks- though very skillful tricks which were impressive. Sometimes they would indicate that it was real magic but I did not know what they meant. Since then I have learned that in an earlier time it was common that magicians claimed they used  real magic.  I still don't quite know what that means, which is just as well since it does not exist.

8) Randi has been sued by people whose tricks he has debunked. Randi seems to have always won.  I say seems to  since legal cases are not as clear cut as mathematics.  I also looked up Uri Geller. He has sued A LOT of people, and not just people who deny his claims. Thinks like using his likeness  without permission  (he may have a point there). Very hard to tell how he is doing on balance.

9) According to Wikipedia Randi dropped out of High School. I assume he learned A LOT on his own.

(Trivia-- who was the last president who did not have a college degree? I will answer at the end.)

10) This seems like a paradox... or something (quoted from Wikipedia):

BEGIN

Randi has been accused of actually using psychic powers to perform acts such as spoon bending. According to James Alcock, at a meeting where Randi was duplicating the performances of Uri Geller, a professor from the University at Buffalo shouted out that Randi was a fraud.  Randi said: "Yes, indeed, I'm a trickster, I'm a cheat, I'm a charlatan, that's what I do for a living. Everything I've done here was by trickery. The professor shouted back:

That's not what I mean. You're a fraud because you're pretending to do these things through trickery, but you're actually using psychic powers and misleading us by not admitting it.

A similar event involved Senator Claiborne Pell, a confirmed believer in psychic phenomena.  When Randi personally demonstrated to Pell that he could reveal—by simple trickery—a concealed drawing that had been secretly made by the senator, Pell refused to believe that it was a trick, saying: "I think Randi may be a psychic and doesn't realize it." Randi consistently denied having any paranormal powers or abilities.

END

Reminds me of this blog entry where I speculate about someone who codes up a great new classical  factoring algorithm and claims he has a quantum computer, or someone who has a working quantum computer and claims its a great new classical factoring algorithm. 

11) The last president who did not have a college degree: Harry Truman.

Fun with birthdays, inspired by Nov 20

 On Nov 20, 2020  the Google Doodle was of Benoit Mandelbrot for his 96th birthday. Why have a Doodle on his 96th bday? Anyway, the Doodle is here.  

On Nov 20, 2020 I read that Joe Biden turned 78. Why no Google Doodle of him? Maybe when he's 96. 

This got me thinking of who else might have a Nov 20 birthday. I found the following (`found' is not quite right as I will explain later).

In order of age. 

Benoit Mandelbrot: Dead at 85, would have been 96

Bobby Kennedy: Dead at 43, would have been 95.

Sergei Novikov: 82 years old. (Won Fields Medal in 1970 and did work on Solitons)

Dick Smothers: 80 years old (Tommy Smothers is not his twin, Tommy  is 3 years older) 

Joe Biden, 78 years old (in most crowds he would be an old-timer, but in this crowd he is the baby of the bunch- though there is a reason for that as you will see later)

There are more Nov 20 famous people (famous to someone- I have not heard of most of them) here

Some thoughts on all of this trivia

1) I keep a list of famous (to me) people over 80 (though if I look someone up who is not quite 80 I may put him on the list anyway, as is the case for Biden and Trump) so if they die I won't be one of those people saying `I thought they were already dead'.  I then began putting people on it who were  already dead so I could find matching bdays. Hence it was easy to find Nov 20 birthdays of people over 80, and one under. 

2) Mandelbrot is more famous than Novikov since Mandelbrot has those pretty pictures. This is not a criticism of his work. Is it possible to make people who do hard and abstract math more in the public eye? Probably not. 

3) There is an awesome song about the Mandelbrot set (though some of the comments on the you tube video say its the Julia Set, but HEY- if they have math in a song, I am happy and don't get too fussy about how accurate it is- though I would understand if Julia fans are annoyed). The song is here. It has 464 likes and 41 dislikes. That always puzzled me- why does it have any dislikes? I've seen really awesome songs still have some dislikes. Well, as Rick Nelson sings in Garden Party (see here) ,you can't please everyone, so you got to please yourself. He got 25,000 likes and 702 dislikes. An awesome ratio, but why are there any dislikes? 

4) I don't think Novikov will have a song about his work anytime soon.

5) Joe Biden has had some novelty songs about him in the past, and will do have more in the future once he is the Whitehouse. (Is the statement `Joe Biden is the president-elect' biased?)

6) I like the variety of the Nov 20 birthdays: two math, two politics, one entertainment. 

7) I originally thought Nov 20 is NOT special and that most days would have around 5 bdays in my files. but actually no- I did a spot check of Nov 21,22,23,24,25,26,27,28,29,30 and they are all either 0,1, or 2 bdays. Prob not significant since this is just my small file. OR people avoid having babies close to thanksgiving (not sure of that one, but people DO avoid Feb 29 and Dec 25). 

8) Of more interest are people born the same DAY and YEAR. I have a few of those, but I will point out one relevant to our field:

Albert Meyer and Art Garfunkel are same DAY and same YEAR.

(ADDED LATER: Art Garfunekl got a BA in Art History and then an MA in Math Eduacation)

Most famous SAME DAY and SAME YEAR of all time? I would guess

Abe Lincoln and Charles Darwin. 

Second place

 Margaret Thatcher and Lenny Bruce.

 (I really doubt that's second place) 

Vaughan Jones and Kaikoura

Vaughan Jones, one of the greatest mathematicians from New Zealand, passed away on September 6 at 67. Jones is an expert in knot theory among other areas and received the Fields Medal in 1990.

The Jones polynomial captures information about knots. Vaughan Jones himself co-authored a paper on a polynomial-time quantum algorithm for approximating the Jones polynomial, one of the few natural problems outside of factoring that has an exponential improvement with a quantum algorithm. 

From his Vanderbilt obituary

One way he worked to improve the field of mathematics in his native country was to organize a “summer school” in January each year and attract leading mathematicians from around the world to give lectures and interact with local students and professional mathematicians at a variety of beautiful locations around New Zealand. Out of this activity grew the New Zealand Mathematics Research Institute, which he co-founded and then led from the mid-1990s to this year.

I had the pleasure of teaching in one of those summer schools in January 2000 in Kaikoura on the South Island. In between the whale watching, mountain hiking, jogging, gorging on mussels, and Maori ceremonies, the NZMRI summer school Aspects of Complexity had short courses to a mix of students and researchers in complexity and logic. I gave some lectures on Kolmogorov complexity that preceded a study of algorithmic randomness in the logic community. Other speakers included Eric Allender on basic complexity, Felipe Cucker on real computation, Mike Fellows on parameterized complexity, and Dominic Welsh on counting complexity. 

It took me 36 hours door-to-door to get to Kaikoura but definitely worth it. Thanks to Vaughan Jones, for his research, his polynomial and creating a summer school that gave me that one perfect week in New Zealand.

Alex Trebek/What is today's post about?

(ADDED on Nov 23: Ken Jennings will be an interim host for Jeopardy, see here.)

 Alex Trebek, long time host of the TV show Jeopardy! (the exclamation point is part of the name, though I will omit it for the rest of the post), passed away in November of 2020 at the age of 80. He announced he had pancreatic cancer in March 2019.

0) Here is a pointer to a page that has all of our posts with the word Jeopardy in them. Some are about the show and others mention the show in passing. All of the posts relate to the TV show. That is because Lance and I lead fairly safe lives.

1) On April Fools day of 1997 Pat Sajak hosted Jeopardy and Alex Trebek hosted Wheel of Fortune. Both are on You tube: Trebek hosts wheel, Pat hosts Jeopardy Alex's hosting was more fun because- well, you can see for yourself. 

2) Aside from that one day, Alex Trebek hosted Jeopardy every night since he began in 1984. 

3) My favorite pangram (sentence that has all 26 letters) is

Watch Jeopardy!, Alex Trebek's fun TV quiz game show. 

(See my post on natural pangrams here for... more natural pangrams and a discussion of what natural means.) 

It's my favorite since I can really imagine someone saying it. The show should have used it for its tagline. And now they can't :-(

4) From Alex's comments he seems to like high scoring games that are not run-a-ways. He also likes when people bet big on the daily doubles and on final Jeopardy.  I think he liked having long win streaks like Ken Jenning's  and James Holzhauer, but see point 7 below.  I think he didn't like it when people go for the high scoring questions first (perhaps looking for the Daily Double) since sometimes the category name is not quite clear (e.g., Country Groups could be things like NATO or things like The Charlie Daniels Band) so you want to do a cheap question to get your feet wet, and also easier for the audience to see what the category means.  IMHO they should really make the Daily Double Uniformly distributed on all the squares instead of having it tend to be the bigger-money questions. 

5) When the final Jeopardy category is  revealed he sometimes says that's a  good category! or that sounds hard.  Makes me wonder that if he makes no comment he is thinking that's a stupid category  or Gee that's easy.

6) Because of the pandemic they could not, for a while, make new shows. Hence  they aired old shows including the  first ever Alex-Trebek-Jeopardy (the show had been hosted by Art Fleming and the Trebek-version was really a reboot). From that show I found out WHY it's called Jeopardy (a question I had never thought about). It's because if you get an answer WRONG you can LOSE money- that's the Jeopardy. Not really a good name, but by now everyone knows the show by that name.

7) Art Fleming also died of pancreatic cancer, back in 1995 (he was 70). Coincidence? Well, yes, though two game show hosts of the same show dying of the same disease 25 years apart could be the premise of a really bad murder mystery. 

8) Alex makes some small talk with the contestants  (though some is edited for time). Things like I hear you have a book on muffins that is not a cookbook-- what's that all about?' I wonder if during Ken Jenning's 74-long winning streak, towards the end,  Alex ran out of things to ask him. I can imagine I hear you're pretty good at Jeopardy.

9) I wonder how good Alex would be playing Jeopardy. When he hosted Wheel of Fortune he said in passing that he would NEVER go on Jeopardy as a contestant, so he doesn't think he would do well. He could be wrong about that since over time they ask questions that are not quite repeats but draw on the same knowledge- and he's heard all of them. However, it could be that he is too busy concentrating on other things to really absorb all of this knowledge. 

10) The we give the answers you give the questions is a bit odd. However, in my classes I  sometimes say  We'll Trebek this - we know what the answer is, we have to find the question.

11) This youtube video is of a contestant singing WORDS to the Jeopardy theme song that he wrote.The contestant  refers to Jon Stewart as having also written words to the Jeopardy theme, but I can't find that anywhere- if you can, let me know. 

12) Weird Al did a novelty song about Jeopardy using Art Fleming in the video (see  here)  I always hoped he would update it and use Alex Trebek. He never did and now he can't :-( OR-with todays technology maybe he can. Here's hoping!

13) Alex Trebek was in a category by himself!

Recovery

Lance: Perhaps we should do a post-election vidcast--what does it mean for complexity!

Bill: Not sure if you are serious- but I doubt a Biden presidency will either speed up or slow down the proof that P NE NP or anything else in complexity. Did Trump give LESS money to the NSF and other funding agencies, and will Biden give more? I doubt it. 

Lance: Trump's budget did call for a massive cut for the NSF but luckily he doesn't control the purse strings. It's the immigration policy that worried me--both that it keeps good students from coming to the US and that it cuts off a revenue source that will cause many good schools to close down.

Bill: Excellent point- but sounds more like a post you could write since you... know stuff, as opposed to a vidcast with me who... doesn't know stuff. 

---

Bill sells himself short and me long but here is my post.

After Trump was elected in 2016 I thought maybe Trump with all his bluster will just be a typical conservative politician that we can live through until the next election. That didn't last long with his travel ban for Iranians just a few weeks after his inauguration when I said "This is not the America I believe in."

Judges have stopped the worst of Trump's travel bans but he has continued to whittle down the number of available visas, made it harder to get visas and get visas after they graduate. New students can't come to America if they take only on-line courses at a time many universities are online. Now students will have to get their visas renewed after two or four years. Few get a PhD in four years and would students come here and take the risk that their visas won't get renewed before they can finish? The CRA has some details on the newest rules. Not to mention Trump's handling of COVID--would you send your kid to America now?

Trump hasn't hidden his disdain for higher education and had he won a second term his policies would greatly diminish the country's academic strength. Biden can and certainly will undo much of these changes and I hope it is not too late. 

More from The Chronicle.

Random Thoughts on the Election (2020)

1) Biden will be the oldest president (measuring by when they take the oath of office), at 78. The next two are Trump 70 and Reagan 69. Biden will be older entering office then Reagan was leaving office. 

After Biden, Trump, Reagan:

William Henry Harrison 68. Why do some people have middle names that are commonly spoken and some do not? Others with middle names spoken: Lee Harvey Oswald, John Wilkes Booth. 

James Buchanan 65

George H. W. Bush 64. Why do some people have their initials commonly spoken and others do not? In this case it may be to distinguish from W. Why are some people known by their middle initial? Well, actually one that I know of, W.

Youngest was Theodore Roosevelt 42 who took the office after McKinley was assassinated . Kennedy was youngest to take the oath after being ELECTED at 43. Theodore Roosevelt was known as TR. John F Kennedy is often called JFK. Franklin D Roosevelt was called FDR. Why are some people known by their initials? In these cases maybe to distinguish them from other Roosevelts and Kennedys.

2) Right now it looks like GA will go for Biden. This surprises me. I had heard `GA is on the verge of turning blue and always will be.'

3) Dem-Blue, Rep-Red always puzzled me since I thought Red was associated with communism.

4) A quote from the Trump/Schwartz  book THE ART OF THE DEAL about why Carter was a one-termer  is rather predictive:

See here

(I've heard Schwartz referred to as a ghost writer. That is not true-- Tony Schwartz's name is ON THE COVER, so he is not a ghostwriter.)

5) During the Trump administration UAE, Bahrain, and Sudan all recognized Israel (gee, when I see it on a map I recognize it, why did it take them so long :-) ). See here. All three deals were brokered by the US so Trump could  take credit here. So why didn't he? One answer is that the left-wing lame stream media didn't cover it much. But FOX didn't cover it much. Trump didn't mention it much. Trump didn't even mention it as a way to complain about media coverage. So- independent of if you think Trump deserves credit here or not, I am interested in why he didn't brag about this one. (When I have asked this question people point out that Trump's base would not care about this. But Trump could complain that Obama got a Nobel Peace prize for nothing, and he got these deals done and hasn't, gotten a Nobel Prize because of the fake-Nobel-Committee and channel this into anti-Obama sentiment.)(ADDED LATER- some of the comments have corrected me and say that Trump DOES mention it-- A LOT. My bad. Still do not know if Fox News mentioned it much.) (ADDED LATER- another comment on my blog pointed to three times Fox News DID talk about this achievement.)

6) Truth avoids imitating  art: Watch Season five of the HBO show VEEP for how m

messy a close election can be. 

7) I think Biden will end up being president and the transition will be peaceful. Why? Fox News and other conservative organizations are urging Trump to concede. Republican state legislators are NOT trying to find ways to overturn the results in their states. Judges have found NO evidence for the kinds of fraud that Trump is complaining about. Many Republicans are silent (John Oliver says that means they SUPPORT  Trumps allegations, but I think it means they are NOT supporting Trump's allegations.) 

 Why is the Republican establishment NOT backing Trumps claims of fraud? Here are some thoughts.

a) Because the allegations of fraud are not just false but obviously false.  

b) Because they think that it is better for the country to have a clean transition.

c) Because they are tired of Trump also and realize he is not good for the party brand (a bit late now).

d) Corrupting the electoral process is a bridge to far. (Where did that phrase come from?)

e) I wonder if Trump himself would have preferred to lose in 2016 and go around having rallies, perhaps have his own TV network. RALLIES are fun, RUNNING THE COUNTRY is not. So those around him may want him to go back to his original plan. 

8) Did Nate (the only pollster with a one-word-name) do well this time around  He thinks so, see here. Its not even clear he did badly in 2016- he gave Trump a 20% chance in 2016 and a 10% chance this time. 

9) I think that if  we had not had a pandemic then  Trump would have won. Two reasons: the country thinks he handled it badly, and it may have literally killed some of his voters.  As a final note on that: Mark Meadows (WH Chief of staff) has COVID. I am surprised Pence didn't get it-- thought maybe he did or will. 

10) Why did people in the Trump WH who one assumes know that Covid is serious and that masks and social distancing were  way to prevent it, not do these simple things?  Perhaps they thought (correctly) that the more people thing about covid, the more likely Trump loses, so they took a risk. Alas, those that trade their health for electability get neither. 

11) Neither Pence nor Harris is particularly young or old as VP's go. 

Youngest: John Breckenridge, 36. Buchanan's VP

Second Youngest: Richard Nixon, 40, Eisenhower's VP

Oldest: Alben Barkley, 71, Truman's VP

Second oldest: Charles Curtis, 69, Hoover's VP

Pence was 57 when took the oath, Harris will be 56. 

12) If Biden wins then on Jan 20 when he takes the oath there will be 5 living Ex-presidents:Carter, Clinton, W, Obama, Trump (assuming they all stay alive until then). This ties the record for most living ex-presidents. See here for my blog post on this. Getting to 6 will be difficult since Carter is 96 years old. 

13) Neither Lance nor I have blogged much about the election, or even about politics. One reason is that whatever I want to say Scott says better (Scott and Lance are the only theory bloggers known by just their first names). I was going to point to Scott's  political blogs but that was hard since he often has blog posts about multiple topics (Like his post about  Mike Pence thinking that the Ind of CH is a sort of relativism that also allows for adultery to be considered okay (see here for Pence's pre-Trump views on adultery)  Actually Scott never blogged about Pence and CH  but after reading his posts they kind of blur in my mind.) I will point to one blog entry of his  that I suspect will NOT be relevant but is still very interesting: Will he go?

14) Trump claimed the polls showing he was behind were false and part of a conspiracy. I am not sure how this conspiracy would work. If people think their candidate is ahead or behind, then does that affect how or if they vote? Do people say `Gee X is winning, I'll vote for them' ? I doubt it. There are two ways such a conspiracy could work (1)  claim was that some candidate was WAY ahead (it would not matter which one) so you should not bother to vote (2)   in a primary where you are voting on who you think will win the general election.  He also claimed that the early returns saying Biden was winning was a conspiracy. Same problem there- how would that work. This isn't just Trump, other politicians in diff  years claim that early-returns saying X is winning might make it harder for Y to win. I can't see how. 

15) Kamala Harris will be the first women, the first African-American, and the first Asian Veep.  Trivia: There has been a Native American Veep- who was it? More trivia- who coined the term Veep? I won't answer these here, but they might be on my Prez Quiz that I will post after the new President is sworn in.  

Can she be BOTH the first African-American and the first Asian? Yes.

16) In my lifetime the election for President was  SETTLED when the losing candidate conceded. This was good for the country's mindset that YES the president is known and even the other candidate agrees. What if Trump does not concede? I doubt this has any practical affect, except that  on Jan 20 he might be trying to arrange a moving van at the last minute. But if the losing candidate does not concede then when is the matter settled?  When the major news venues say it is? Which ones are major? What if there was a really close election and diff news networks declared diff candidates to have won? This does not seem to be a problem for this election cycle, but it is a question: When is the matter SETTLED in that the country ACCEPTS the result, if the losing candidate does not concede?

(ADDED LATER- I didn't realize how much the TRANSITION matters-- so Trump not letting the transition happen is dangerous.)

17) Carter beat incumbent Ford, but they became friends. Clinton beat incumbent Bush Sr, but they became friends. This is understandable in that so few people are president so they have a shared experience. I doubt that Trump and Biden will become friends.

18)   Bill Clinton's staff removed W's from the typewriters and did some other damage before W moved into the WH see here.  This is NOT a tradition, nor is it acceptable in any way, shape. or form.  I do not know of any other similar cases in America (if you do, let me know in the comments).  I wonder if Trump will do damage  to the WH before he leaves. Do presidents put a deposit down on the WH so that any damage they do, they pay for? I  doubt it, but it would be a good idea. 

19)  Obama and Trump had a cordial 90 minute meeting, see here, after Trump won but before he moved in. This makes perfect sense--outgoing presidents know stuff and have experiences worth sharing with the next president.   Obama said North Korea would be a problem and it is (Trump later tried to spin this--`Obama said it would be hard, but it was easy') I wonder if Trump and Biden will have any kind of meeting, cordial or not. 

20) Every state that went for H Clinton in 2016 went for Biden in 2020. The following states went for Trump in 2016 but went for Biden in 2020: Wisc, Mich, PA, AZ, and maybe Georgia and maybe NC (frankly I doubt NC). There was a plausible  scenario (I forget what it was) where Biden would have won 270-268. 

21) Did Third parties matter? In PA the Libertarian Candidate Jo Jorgenson got 1.1% of the vote which was larger than the diff between Biden (49.7) and Trump (49.1) (The Green party either wasn't on the ballot or got so few votes it was not counted). If most of the Libertarians voted for Trump then he would have won PA and possibly the election. However, Trump is not really a Libertarian, so I doubt that would have happened As for the entire country: (1) . The Libertarians got 1.14% of the total vote in 2020, as opposed to 3.25% in 2016, (2)  The Green party got 1.06% in 2016 and 0.02% in 2020. 

21) I was not particular impressed with the satires of the debates and other political satire on SNL this year. Not sure why- maybe Trump is too wild  to satirize and Joltin Jo is too boring. But the following I DID like and is now more relevant. Watch the whole thing since the first half looks like a real ad.

here

I polled my class about the election

 In 2016 I had the Sophomore discrete math class do a poll of who they wanted for president.

In 2020 I had the  both my  Senior Crypto class and Clyde's Sophomore algorithms course do a poll of who they wanted for president.

All of these polls were anonymous. One big difference- in 2016 it was paper, they could check offwho they wanted or put in a write in, whereas in 2020 it was on elms without a mechanism for a write in--- so no votes for Bernie or Bill or Kruskal (not sure if they were voting for the man or the algorithm) were possible. In all cases I included everyone who was on the Maryland Ballot (so Libertarian and Green votes were possible). 

Discrete Math 2016: 428 students took the poll. Write ins allowed. 

Clinton- 305 which is 71%

Trump- 44 which is  10%

Johnson (Libertarian)- 21 which is 5%

Stein (Green)-  11which is 3%

Sanders-6 which is 1%

Silly answers: 41 which is 10%

I was NOT surprised that Trump got 44 votes- every year I do this and every year the 

republican gets between 10 and 20 percent. Romney go 17% in 2012 (see here). 

Algorithms, 2020, 161 students took the poll

Biden: 127 (79%)

Trump: 25 (16%)

Hawkins (Green): 4 (2%)

Jorgenson (Libertarian): 4 (2%)

Segal (Bread and Roses Party) 1 (1%)

Cryptography in 2020: 

Biden- 40 which is 78%

Trump-6 which is 12%

Hawkins (Green ) 3 which is 6%

Jorgenson (Libertarian) 2 which is 4%

Segal (Bread and Roses) 0 which is 0%

I have no idea what these numbers mean. College students tend to be liberal- we knew that. That Trump went from 10% to 16% would be interesting if it was a larger sample size. I wonder if forcing them to NOT have a write-in had an effect. 

2020 Fall Jobs Post

My annual fall jobs posts, giving advice to PhDs looking for faculty positions, were getting repetitive. See last year's post for the usual stuff and feel free to post opportunities in the comments on this post. This year let's talk about what's changed.

First something you might have missed--the latest Taulbee Survey shows a small drop in the number of new undergraduate CS majors in 2019 after years of massive growth. Is it a simple blip or have we hit the saturation point? We may never know because of the change you definitely didn't miss seeing.

So let's talk about the effect of COVID. We're seeing a large drop in new international students who are having a hard time getting visas or just avoiding the US like the plague (literally). Not sure those numbers will fully come back given other alternatives and a changing international relationship particularly with China. Many undergrads have delayed college and some may never attend. 

On the other hand, COVID has accelerated digitizing the economy, from videoconferencing to in-home entertainment and games to remote access to work environments. The post-COVID economy could create even a larger demand for computer scientists. 

Many universities curtailed hiring last year worried and may do so in the spring given the uncertain budget situation due to the virus. Others continue to hire in computing, some to make up for last year. I just can't make a prediction for the upcoming year but I wouldn't rush to the job market if you have the option to wait. Last year the CRA reinstated the CIFellows, postdocs to help those in a tight job market, and may do so again next year. The CRA will also repeat its CV database.

Late spring interviews in 2020 went virtual and will likely go virtual again in 2021. Nevertheless take the zoom meetings seriously. Make sure your interview talk is still a discussion--answer questions people give in the chat. Still do your research to have strong conversations with everyone you talk to, especially the non-theorists. And still dress nicely, at least from the waist up. Putting on a sports coat is not a bad idea. 

Though most places continue to focus on data science/ML, cybersecurity and to some degree quantum, Rutgers is specifically looking for a hire in computational complexity. Don't see that everyday. 

Do not become obsessed with the Polls unless...

I know someone who checks the polls 3 times a day to see who looks like they will be elected prez. She cares A LOT about the election. It is irrelevant to this post who she supports. 

I've asked her `if you find out that, say, Biden is up  8 points instead of 9 in Penn. or that Georgia is looking pretty safe for Trump, or that Texas is in play (really?) how will that change your life? What will YOU do differently?'

She had no answer. Unfortunately she is still a poll-watcher (I know that means something else usually, but you know what I mean.)

So who should be poll-watching or poll-obsessing?

1) To be fair to my friend, she might decide to GIVE MORE to her candidate if the polls are saying that he will lose (whoops- by saying `he' I gave away that her candidate is NOT Jo Jorgenson- Libertarian).  I doubt my friend could say to the campaign `I want to you to spend it in state X since I read that its close there' (I read that some big donors in 2016 demanded more say in where the money was spend. I doubt that's a good idea since I suspect the party knows more about how to best spend the money then the donor does.) 

2) The Biden and the Trump Campaigns SHOULD be poll-watching to decide where to put their efforts. And I suspect they are doing just that.

3) A really big donor (my friend is not one of those) MIGHT want to poll watch to decide if the candidate they want needs money. (I wonder if EITHER candidate needs money since they get so much free media.)

4) Nate Silver-being a poll-watcher is kind-of his job. And of course writing columns about them and making predictions based on what he sees. My friend is not Nate Silver. 

5) Other people who have Nate Silver's job. I can't name any- is Nate Silver the most famous... Gee, not sure what job title he has... SO this is now two questions: What is his job title, call it X, and is he the most famous person who does X?

SO- my point- DO NOT be a poll-obsessive unless the information you get will lead to an action you can take. And I suspect that mostly it does not. 

The primaries are different: If a poll says A can beat X but B cannot beat X, that might guide who you vote for. 

Misc thought: 

 I've heard the phrase `democratic pollster' and `republican pollster' These terms do not make sense. Would I call myself a `democratic Muffin Mathematician' ? My political leanings do not affect my search for truth about mathematical Muffins. Similarly, one would think that a pollster wants to find the TRUTH, even if its bad news for their employer, ESPECIALLY if its bad news for their employer, so they can help their employer fix it. The phrase `pollster employed by the X party' would make more sense-- however, whenever they are on TV they seem to always say that their candidate is doing well, even when they are not. 

ADDED LATER: Lance had a great tweet about this post: do not obsess about polls, but DO obsess bout prediction markets. I think in the past prediction markets have been better predictors but some group-think has set in so its no longer clear. (I could be wrong- but thats why I have heard.) 

Nature vs Nurture close to my birthday

 Since I was born on Oct 1, 1960 (that's not true---if I posted  my real birthday I might get my  identity stolen), I will do a nature vs nurture post based on my life, which seems less likely to offend then doing it on someone else's life. I'll just rattle off some random points on Nature vs Nurture.

1) Is it plausible that I was born with some math talent? Is plausible that I was born with some talent to understand the polynomial van der Warden theorem? What is the granularity of nature-given or nurture-given abilities?

2) My dad was a HS English teacher and later Vice-Principal. My mom taught English at a Community college. Readers of the blog might think, given my spelling and grammar, that I was switched at birth. My mom says (jokingly?) that I was switched at birth since she thinks I am good at math.

a) I am not THAT good at math. Also see next point.

b) While there are some math families, there are not many. See my post here.

c) I think being raised in an intellectual atmosphere by two EDUCATORS who had the money to send me to college and allowed me the freedom to study what I wanted to  is far more important than the rather incidental matter of what field I studied.

d) Since my parents never went into math or the sciences it is very hard to tell  if they were `good at math' or even what that means.

3) There were early signs I was INTERESTED in math, though not that I was good at it.

a) In fourth grade I wanted to know how many SECONDS were in a century so I spend some time figuring it out on paper. Did I get the right answer?  I forgot about leap years.

b) I was either a beneficiary of, or a victim of, THE NEW MATH. So I learned about comm. and assoc. operations in 8th grade. We were asked to come up with our own operations. I wanted to come up with an operation that was comm. but not assoc. I did! Today I would write it as f(x,y) = |x-y|. This is the earliest I can think of where I made up a nice math problem. Might have been the last time I made up a nice math problem AND solved it without help. 

c) In 10th grade I took some Martin Gardner books out of the library. The first theorem I learned not-in-school was that a graph is Eulerian iff every vertex has even degree. I read the chapter on Soma cubes and bought a set. (Soma cubes are explained here.) 

d) I had a talent (nature?) at Soma Cubes.  I did every puzzle in the book in a week, diagrammed them, and even understood (on some level) the proofs that some could not be done. Oddly I am NOT good at 3-dim geom. Or even 2-dim geom.  For 1-dim I hold my own!

e) Throughout my childhood I noticed odd logic and odd math things that were said: 

``Here at WCOZ (a radio station) we have an AXIOM, that's like a saying man, that weekends should be SEVEN DAYS LONG'' (Unless that axiom resolves CH, I don't think it should be assumed.) 

``To PROVE we have the lowest prices in town we will give you a free camera!'' (how does that prove anything?) 

``This margarine tastes JUST LIKE BUTTER'' (Okay-- so why not just buy butter?)

e) In 9th grade when I learned the quadratic formula I re-derived it once-a-month since I though it was important that one can prove such things.  I heard (not sure from where) that there was no 5th degree equation. At that very moment I told my parents:

I am going to major in math so I can find out why there is no 5th degree equation.

There are worse things for parents to hear from their children. See here for dad's reaction. 

f) When I learned that the earth's orbit around the sun is an ellipse and that the earth was one of the foci, I wondered where the other foci is and if its important. I still wonder about this one. Google has not helped me here, though perhaps I have not phrased the question properly. If you know the answer please leave a comment. 

g) I also thought about The Ketchup problem and other problems, that I won't go into since I already blogged about them  here

4) I was on the math team in high school, but wasn't very good at it. I WAS good at making up math team problems. I am now on the committee that makes up the Univ of MD HS math competition. I am still not good at solving the problems but good at making them up. 

5) From 9th grade on before I would study for an exam by making up what I thought would be a good exam and doing that. Often my exam was a better test of knowledge than the exam given. In college I helped people in Math and Physics by making up exams for them to work on as practice. 

6) I was good at reading, understanding, and explaining papers. 

7) I was never shy about asking for help. My curiosity exeeded by ego... by a lot!

8) Note that items 5,6, and 7 above do not mention SOLVING problems. The papers I have written are of three (overlapping) types:

a) I come up with the problem, make some inroads on it based on knowledge, and then have people cleverer (this is often) or with more knowledge (this is rarer) help me solve the problems.

b) I come up with the problem, and combine two things I know from other papers to solve it. 

c) Someone else asks for my help on something and I have the knowledge needed. I can only recall one time where this lead to a paper. 

NOTE- I do not think I have ever had a clever or new technique. CAVEAT: the diff between combining  known knowledge in new ways and having a clever or new technique is murky. 

8) Over time these strengths and weaknesses have gotten more extreme. It has become a self-fulfilling prophecy where I spend A LOT of time making up problems without asking for help, but when I am trying to solve a problem I early on ask for help. Earlier than I should? Hard to know. 

9) One aspect is `how good am I at math' But a diff angle is that I like to work on things that I KNOW are going to work out, so reading an article is better than trying to create new work. This could be a psychological thing. But is that nature or nurture?  

10) Could I be a better problem solver? Probably. Could I be a MUCH better problem solver? NO. Could I have been a better problem solver  I did more work on that angle when I was younger? Who knows? 

11) Back to the Quintic: I had the following thought in ninth grade, though I could not possibly have expressed it: The question of, given a problem, how hard is it, upper and lower bounds, is a fundamental one that is worth a lifetime of study. As such my interest in complexity theory and recursion theory goes back to ninth grade or even further. My interest in Ramsey Theory for its own sake (and not in the service of complexity theory) is much more recent and does not quite fit into my narrative. But HEY- real life does not have as well defined narratives as fiction does. 

12) Timing and Luck: IF I had been in grad student at a slight diff time I can imagine doing work on  algorithmic  Galois theory. Here  is a talk on Algorithmic  Galois theory. Note that one of the earliest results is by Landau and Miller from 1985---I had a course from Miller on Alg. Group Theory in 1982. This is NOT a wistful `What might have been' thought. Maybe I would have sucked at it, so its just as well I ended up doing recursion theory, then Ramsey theory, then recursion-theoretic Ramsey Theory, then muffins. 

50 Years of PBS

The Public Broadcasting Service (PBS) launched fifty years ago this month in the United States. The New York Times talks about its fifty reasons how the network mattered. I'll throw in my thoughts.

I was just slightly too old for shows like Sesame Street, Electric Company, Mr. Rogers and Zoom, not that that stopped me from watching them. My kids grew up on Barney and Friends. My daughter even had a toy Barney that interacted with the show, which went as well as you'd expect. 

PBS introduced me to those great British TV shows for young nerds like me including Monty Python and Doctor Who. I wasn't into Nova but did watch Carl Sagan's Cosmos religiously in high school.

My favorite PBS show was the American Experience, short documentaries about US culture. I remember learning about this history of Coney Island and the quiz show scandals before Robert Redford made a movie about it.

Siskel and Ebert got their start on PBS and became my go to source for movie reviews.

In 1987 PBS broadcasted Ivy League football games. One Saturday I sat down expecting to watch my alma mater and instead got supreme court hearings. Only on PBS could Cornell football get Borked.

Hugh Woodin, Kurt Godel, Dwayne `The Rock' Johnson, Robert De Niro, David Frum, Tom Selleck: Do I care what they think? Should I?

 MATH:

My last post on CH mentioned that Hugh Woodin used to think NOT(CH) but now thinks CH. In both cases his reasons have some math content to them. Also, note that Hugh Woodin seems to believe that CH somehow HAS an answer. Kurt Godel also thought CH HAS an answer. It has been said that he could have announced  his result that CH is consistent by saying  L is THE model, and the problem is now solved. 

Should we care what Hugh Woodin and Kurt Godel think about CH?

YES- they have both studied the issue A LOT. If you think CH should have an answer, then surely you would care what they think. 

NO-  CH has no answer so there opinions are no better than mine. If you think CH does not have an answer then you might think this; however, I think you should still be at least INTERESTED in what people who have thought about the problem A LOT have to say, even if you will disagree with them.

But with MATH there are people who clearly know more than you on topics you care about, so it is worth hearing what they have to say. 

POLITICS:

Recently Dwayne THE ROCK Johnson (by Wikipedia: actor, producer, businessman, and former professional wrestler) ENDORSED Joe Biden. Should we care about his opinion? Maybe, if wrestling fans and former pro wrestler tend to be Republicans, so this may indicate a shift. I do not know if this is the case. 

Robert De Niro was in favor of impeaching Donald Trump. He also said that Trump was like a Gangster. He would know because he was in the movie GOODFELLOWS and later THE IRISHMAN (about Jimmy Hoffa). To be fair I do not think he said that is how he would know. Even so, I don't think I care what he thinks, unless he has some specialized knowledge I do not know about. 

David Frum is a republican who had a break with the party NOT over Donald Trump, but over Obamacare- which you may recall was originally a CONSERVATIVE response to Hillarycare by the Heritage Foundation.  He has a good article on this here. Because he is an intelligent  republican in favor of Obamacare (or some version of it) he is worth listening to.

In POLITICS its trickier- who is worth listening to and why. For all I know, THE ROCK has made a detailed study of the Republican and Democratic platforms (actually this cannot be true since the Republicans did not have a platform this time). 

COMMERCIALS:

Tom Selleck (Actor-Magnum PI a while back, Blue Bloods now)  does commercials for reverse mortgages. A while back I asked a group of people WHY he is doing them. Here were some answers and reactions

a) He needs the money. Not likely, he seems to have done well and does not seem to have the kind of bad habits (e.g., drugs) that need money. Maybe he has expensive tastes (my only expensive tastes is in fine European Kit Kat bars--- which actually are not that expensive). 

b) He likes doing commercials. Maybe.

c) He believes in the product. At this, everyone cracked up in laughter.

This raises a more general point: Why does ANYONE believe ANY commercial since we KNOW the actor is being PAID to say it. I ask non rhetorically as always. 

Revisiting the Continuum Hypothesis

I have been thinking about CH lately for two reasons

1) I reread the article

Hilbert's First Problem: The Continuum Hypothesis by Donald Martin from Proceedings of Symposia  in Pure Mathematics: Mathematical developments arising from Hilbert Problems. 1976. (For a book review of the symposia and, The Honor Class, also about Hilbert's problems, see here.)

The article takes the point of view that CH CAN have an answer. He discusses large cardinals (why assuming they exist is plausible, but alas, that assumption does not seem to resolve CH) and Projective Det.  (why assuming it is true is plausible, but alas, that assumption does not seem to resolve CH).

(A set A \subseteq {0,1}^omega is DETERMINED if either Alice or Bob has a winning strategy in the following non-fun game: they alternate picking bits a_1, b_1, a_2, b_2, ... with Alice going first. If a_1 b_1 a_2 b_2... IS IN A then Alice wins, IF NOT then Bob wins. Martin showed that all Borel sets are determined. Proj Det is the statement that all projections of Borel sets are determined. AD is the axiom that ALL sets A are determined. It contradicts AC.)

But what really inspired this post is the last paragraph:

Throughout the latter part of my discussion, I have been assuming a naive and uncritical attitude towards CH. While this is in fact my attitude, I by no means wish to dismiss the opposite viewpoint.  Those that argue that the concept of set is not sufficiently clear to fix the truth-value of CH have a position that is at present difficult to assail. As long as no new axiom is found which decides CH, their case will continue to grow stronger, and our assertions that the meaning of CH is clear will sound more and more empty.

2) Scott Aaronson mentioned in a blog post (see here) that  he has read and understood the proof that CH is independent of set theory.

SO, this seemed like a good time to revisit thoughts on CH.

 I took a very short poll, just two people, about CH: Stephen Fenner (in a perfect world he would be a set theorists) and Scott Aaronson (having JUST read the proof that CH is ind.  he has thought about it recently).

Here are some thoughts of theirs and mine

1) All three of us are Platonists with regard to the Naturals (I was surprised to find recently that there are people who are not!) but not with regard to the reals.  So we would be OKAY with having CH have no answer.

2) All three of us  agree that it would be nice if SOME axiom was both

a) Intuitively appealing or aesthetically appealing ,  and

b) resolved CH.

I always thought that (a) would be the hard part-- or at least getting everyone (not sure who we are talking about) to AGREE on a new axiom. But even getting an axiom to resolve CH seems hard.  Large cardinals don't seem to do it, and various forms of Determinacy don't seem to do it.

Scott reminded me of Freiling's Axiom of Symmetry (see here) which IS intuitive and DOES resolve CH (its false) though there are problems with it--- a minor variant   of it contradicts AC (I am QUITE FINE with that since AC implies Banach-Tarski which Darling says shows `Math is broken'.)

Stephen recalled some of Hugh Woodin's opinions of CH, but Hugh seems to have changed his mind from NOT(CH): 2^{aleph_0} = aleph_2, to CH:  2^{aleph_0} = aleph_1.(See here.)

3) All three of would be okay with V=L, though note that this would put many set theorists out of work. All the math that applies to the real world would still be intact.  I wonder if in an alternative history the reaction to Russell's paradox would be a formulation of set theory where V=L. We would KNOW that CH is true, KNOW that AC is true. We would know a lot about L but less about forcing.

4) Which Geometry is true: Euclidian, Riemannian, others? This is now regarded as a silly question: Right Tool, Right Job! If you build a bridge use Euclid. If you are doing astronomy use Riemann. Might Set Theory go the same way? It would be AWESOME if Scott Aaronson found some quantum thing where assuming 2^{aleph_0} = aleph_2 was the right way to model it.

5) If I was more plugged into the set theory community I might do a poll of set theorists, about CH. Actually, someone sort-of already has. Penelope Maddy has two excellent and readable articles where she studies what set theorists believe and why.

Believing The Axioms I: here

Believing The Axioms II: here

Those articles were written in 1988. I wonder if they need an update.

MIP* = RE Redux

Everything pre-covid seems at least five years ago to me, so it's hard to believe that MIP* = RE is a 2020 result. To remind you, consider the model where we have two powerful provers put in separate rooms where they can't communicate (think suspects of a crime put in separate interrogation rooms). An computationally efficient verifier can ask them questions based on random coins. Thirty years ago, Laszlo Babai, Carsten Lund and myself showed that every language in nondeterministic exponential time has proofs in this model.

Now suppose the provers have entangled quantum bits. This question has a long history that culminates in the MIP* = RE paper earlier this year by Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen showing that every proof of any length can be proven in this model. Incredible!

But wait, why is there a new version 2 dated last week? Turns out the MIP* = RE paper relied on a 2016 paper by Vidick which was later discovered to have a bug. No worries, as the authors of the MIP* = RE paper got around this issue by a quantum analysis of a low-degree test from that old Babai-Fortnow-Lund paper.

Vidick's blog post explains it all, including the angst of a major result falling apart temporarily. He has good company. Glad it all worked out. 

A Quote from Tesla which is very predictive in one way, and perhaps not in another way

 Nikola Tesla, famous inventor, who lived 1856--1943 said the following:

When wireless is perfectly applied the whole earth will be converted into

a huge brain, which in fact it is, all things being particles of a real

and rhythmic whole. We shall be able to communicate with one another

instantly, irrespective of distance. Not only this but through television

and telephony, we shall see and hear one another as perfectly as though

we were face to face, despite intervening distances of thousands of miles;

and the instruments through which we shall be able to do this will be

amazingly simple compared with our present telephone. A man will be able to

carry one in his vest pocket.

The `vest pocket' at the end really impressed me.

By `a man will be able to carry one...' I don't know if he mean all people or if he actually 

meant that women would not need such a device. If that is what he meant then,

while high marks for tech-prediction, low marks for social-prediction. 

This quote is SO right-on for technology that I offer the following challenge: Find other quotes from year X that were very predictive for year X+Y for a reasonably large Y.

ADDED LATER: I will give two answers to my own challenge:

1) On the TV show THE HONEYMOONERS, in 1955, Ralph Cramden predicts 3-Dim TV. I blogged about that here

2) Did the TV show Get Smart foreshadow cell phones. Maxwell Smart's shoe-phone was portable but wearing it on his foot seems odd. It also used dial, not touch tone. Mel Brooks (co-creator of the series) points out that in the Pilot episode Max is enjoying a show and his phone goes off so he has to leave and take the call -- which was very strange then but standard now. So the show did predict one of the problems with cell phones, if not cell phones themselves. 

Remembering 2000

FOCS 2000 took place in Redondo Beach, just south of Los Angeles, November 12-14. Certainly some great results such as the Reingold-Vadhan-Wigderson Zig-Zag Graph Product Expander construction that would lead to Omer Reingold's Undirected Connectivity in Log Space. Mostly though I remember the discussions about the presidential election held the week before and whether we might find out our next president during the conference. Spoiler alert: We didn't. 

Consider the following viewpoints for a person X

1. Did X support Bush or Gore?

2. Did X interpret the rules of the election that Bush won or Gore won?

These should be independent events. Your interpretation of the rules should not depend on who you supported. But in fact they were nearly perfectly correlated. Whether you were a politician, a newspaper editorial page writer, a supreme court justice, a computer scientist or pretty much everyone else, if you supported Gore, you believed he won the election and vice-versa. Everyone had their logic why they were right and I'm sure my readers who remember that election still believe their logic was correct. 

As this upcoming election gets messy, as it already has, take care with trying to justify your desired endgame by choosing the logic that makes it work. Would you use the same logic if the candidates were reversed? Everyone says "yes" but it's rarely true. Just like Mitch McConnell, you'll just find some excuse why the opposite situation is different. Trust me, my logic is impeccable. 

Baseball can go on forever, it doesn't just seem that way

 Most games have some way to make sure they cannot go on forever.

1) Chess: I had thought there was a 50-move rule and a 3-times-same-position rule, but its a byte more complicated than that, see here. There is also a chess clock. Suffice to say, Chess can never on forever (though it may seem like it does). 

2) NIM: Eventually all of the stones are gone. There may be more complicated versions where you can add some stones, but in those versions I suspect that there is some parameter that goes to 0.

3) Basketball, Football, Hockey, Soccer: These all have a clock so they are time limited. For overtime there are also rules that make sure the game cannot go on forever. Or maybe its just very rare: what if the Superb Owl (spelled that way to avoid lawsuits, see here) is tied 0-0 at the end of the four quarters and goes into overtime and... nobody scores... ever. Could the game go on forever or would the referees declare it a tie? In the regular season there are ties, but in the in the superb owl? Actually this may be more a problem in the playoffs since you need to determine who goes to the next round.

4) Take your favorite game. I would bet dollars to doughnuts (what an odd phrase---see here for more about the phrase) that there is some mechanism to make sure the game ends. An exception that Darling pointed out to me: If in Gin Rummy both players are terrible then the game can go on forever. This is probably true for other games as well and actually makes the question into two questions (a) will a game terminate no matter what the players do, and (b) (not sure how to formalize) will a game terminate if both players are trying to win and are making reasonable moves.

You may have noticed that in item 3 I left out Baseball. There is no clock in baseball. So one way the game can go on forever is to have a tie and extra innings and nobody scores. I think the umpire has the authority to call it a tie. (Incidentally, the shortened baseball season has a new extra inning rule---each inning starts with a runner on second. See here,) When Lance read an earlier version of this post he pointed me to 5 ways a game can go on forever, not counting the example I have later in this post. Here is where Lance found the question and answer (look on the first page under Speed Department for the question, and the very end of the second page for the answer). I also did my own writuep with more details, see here.  Also of interest (though not if you were actually at the game this happened), the record for number of times a player has a foul with 2 strikes is 16, see here. 

 However, I came across an  example more obscure than any of those. 

Here is what happened (and you can see the video of it here, though it really starts about a minute into it. Keep reading- it looks like its another post, but its part of this post: 

From your Digest

Zev Steinhardt

·

July 9, 2019

Studied at Pace University

Has a play ever happened in baseball that was so out of the ordinary that no written umpiring rule at the time covered it?

Back in 2008, the Yankees drafted a pitcher named Pat Venditte. What made Venditte unusual is that he can throw with both hands. In other words, he’s a switch pitcher. When he was drafted, he was assigned to the Staten Island Yankees, a low A ball team.

In his first game (against the Mets farm team, the Brooklyn Cyclones), Venditte came in to pitch. After getting the first two batters out and giving up a single, he then faced Ralph Henriquez, was a switch hitter. What happened next resembled an Abbott and Costello comedy routine. Venditte would put the glove on one hand (he had a specially made glove that could be worn on either hand) and Henriquez would then step across the plate to bat from the other side. Venditte would then switch his glove hand again and Henriquez went back to the other side.

Eventually, after much discussion, the umpires ruled that Henriquez would have to choose a batting side first, before Venditte had to commit. Henriquez was mad and, after he struck out, he slammed the bat against the ground in frustration.

The umpires were, in essence, winging it, because there was no rule to cover the situation. Eventually, the higher ups in baseball did write a rule to cover the situation — the opposite of the umpires’ decision.