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.