Complexity Year in Review 2019

Some great theorems this year including non-deterministic double exponential time by quantumly entangled provers and integer multiplication in O(n log n) time. But the result of the year has to go to a paper that gave a shockingly simple proof of a major longstanding conjecture.

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture by Hao Huang

Of course 2019 will be remembered in some circles for giving us Google's claims of quantum supremacy and all the quantum hype, deserved and otherwise, that goes with it.

Personally Bill came out with his new book Problems with a Point; Exploring Math and Computer Science co-authored with Clyde Kruskal (Amazon, blog posts). Lance became a dean. 

We remember Michael Atiyah, Elwyn Berlekamp, Charles van Doren, Ray Miller, Jérôme Monnot and Nils Nilsson.

Thanks to guest posters Abhinav Deshpande, Evangelos Georgiadis, Samir Khuller, Ming Lin, David Marcus, Ben Shneiderman and John Tromp.

As we move into the 2020s, we tend to look back and look forward. The 2010s will go down as the decade computing and data transformed society, for better and worse. Google turned 21 this year as its OG leadership stepped down. I turned 21 in 1984, but 1984 seems closer than ever.

Last year we ended the year in review by 

We end the year with craziness, the stock market is going through wild gyrations, we have a partial government shutdown including all of NSF and an uncertain political landscape with different parties leading the two houses of congress. We're still in the midst of a technological revolution and governments around the world try to figure how to regulate it. I find it hard to predict 2019 but it will not be quiet.

2019 was not quiet and we're about to head into an impeachment trial, Brexit and a critical US presidential election. The real challenges of the twenties will come from massive transformation from automation, climate change and deepening divisions in our society. How will academia cope with changing demographics, financial challenges and educating to manage the technological revolution?

Let's all take a deep breath, roll up our sleeves and get the decade going.

Why is there no all-encompassing term for a course on Models of Computation?

In my last blog post I asked my readers to leave comments saying what the name of the course that has some of Regular Languages, Context Free Languages  Decideability, P, NP (any maybe other stuff) in it.  I suspected there would be many different names and their were. I was able to put all but 6 into 4 equivalence classes. So that's 10 names. Thats a lot  especially compared to

(Introduction to) Algorithms

and

(Introduction to) Cryptography

which I suspect have far fewer names. One commenter pointed out that the reason for the many different names is that there are many versions of the course. That's not quite an explanation since there are also many different versions of Cryptography---at UMCP  crypto is cross listed in THREE departments (CS, Math, EE) and its taught by 6 or so different people who don't talk to each other (I am one of them). I think Algorithms is more uniform across colleges.

I think that terms Algorithms and Cryptography are both rather broad and can accommodate many versions of the courses, whereas no term seems to be agreed upon to encompass the DFA etc course.
Even saying DFA etc is not quite right since some of the courses spend little or even no time on DFA's.

Below is a list of all the names I got and some comments. Note that some schools appear twice since they have two courses along these lines.

-----------------------------------------
TITLE: (Introduction to) Theory of Computation:

Swarthmore:                                            Theory of Computation

UCSD:                                                     Theory of Computation

Saint Michaels:                                        Theory of Computation

Univ of Washington: Introduction to the Theory of Computation

Waterloo:                  Introduction to the Theory of Computing

COMMENT: Theory of Computation could have been the term that encompasses all of these courses. I speculate that it didn't catch on since it sounds too much like computability theory which is only one part of the course.

------------------------
TITLE: Formal Languages and XXX

CMU:                                                Formal Languages, Automata, and Computability

Florida Tech:                                    Formal Languages and Automata Theory

UC-Irvine:                                        Formal Languages and Automata Theory

Univ of Chicago:    Introduction to Formal Languages

University of Bucharest:                 Formal Language and Automata

TU Darmstadt:                                Formal Foundations of CS I: Automata, Formal Languages, and Decidability

TUK Germany:                               Formal Languages and Computability

COMMENT: The title makes it sound like they don't cover P and NP. I do not know if thats true; however, I speculate that, it could never be the encompassing term.

Spell Check things Automata and Computability are not words, but I've googled them and they seem to be words.

--------------------------
TITLE: Computability/Decidability and Complexity/Intractability

Reed College: Computability and Complexity

Caltech:          Decidability and Intractability

COMMENT: The title makes it sound like they don't cover regular or context free languages. I do not know if that's true; however, I speculate that, since the terms sound that way, they never caught on as the general term.

Spellecheck thinks that neither Decidability nor Decideability is a word. Google seems to say that I should leave out the e, so I will.

------------------------------
TITLE:  Blah MODELS Blah

Tel-Aviv (a long time ago) Computational Models

UIUC:                               Algorithms and Models of Computation (also has some algorithms in it)

Waterloo:                                                   Models of Computation (enriched version)

COMMENT: Models of Computation sounds like a good name for the course! Too bad it didn't catch on.  It would also be able to withstand changes in the content like more on parallelism or more on communication complexity.

------------------------------
TITLE: MISC

CMU:                                          Great Ideas in Theoretical Computer Science

UCLouvain (Belgium)                Calculabilite (Computability)

Moscow Inst. of  Phy. and Tech.: Mathematical logic and Theory of Algorithms

Portland State University:            Computational Structures

Germany:                                     Informatik III (Not all of Germany)

Univ of Chicago:                         Introduction to Complexity

COMMENT: All of these terms are to narrow to have served as a general term.

What do you call your ugrad non-algorithms theory course?

I am in the process of reviewing

                     What can be computed: A Practical Guide to the Theory of Computation
                     by John MacCormick


and I need YOUR help for the first SENTENCE.  I began by saying


                    This is a text book for a course on Formal Language Theory

but then I realized that this is not what we call the course at UMCP. Then I got to thinking: what do other schools call it? I have the following so far:

UMCP: Elementary Theory of Computation

Harvard: Introduction to Theory of Computation

MIT: Automata, Computability, and, Complexity

Clark: Automata Theory

(My spellcheck does not think Automata is a word. Also Computability. Usually I listen to my spellcheckers, but I checked and YES, I spelled them right.)

For some other schools I either hit a place I needed an account, or I just got titles without a description so I could not be sure.

This is where YOU come in!

Please leave comments with your school and the title of the course at your school that covers a reasonable overlap with: Regular Sets, Context Free Sets, Decidable and Undecidble and r.e. sets, P, NP, perhaps other complexity classes, and NP-completeness. Its FINE if your answer is one of the above ones, or one of the other comments--- I plan to later set this up as a pigeonhole principle problem.

I suspect that courses in algorithms are called Algorithms or Introduction to Algorithms.

I suspect that courses in cryptography are called Cryptography  or Intro to Cryptography.


Why does the non-algorithm, non-crypto theory course have more names?

Julia Robinson's 100th birthday

On Dec 8, 1919 Julia Robinson was born, so today is close to her 100th birthday (she passed away at

the age of 65 on July 30, 1985).

So time for some facts about her

1) She got her PhD from Tarski where she proved the undecidability of the theory of the rationals.

2) She is probably best known for her work on Hilbert's tenth problem (which we call H10)

In todays' terminology H10 would be stated as:

Find an algorithm that will, given p in Z[x_1,...,x_n] determine if it has an integer solution.

Hilbert posed it to inspire deep research in Number Theory. There are some cases that are

solvable (the topic of a later blog post) but the general problem is undecidable. This is not what Hilbert was aiming for. I wonder if he would be happy with the resolution.

The Davis-Putnam-Robinson paper showed that the decision problem for exponential diophantine equations was undecidable. It was published in 1961. The paper is here.  Martin Davis predicted that the proof that H10 was undecidable would be by a young Russian mathematician. He was proven correct when Yuri Matiyasevich supplied the missing piece needed to complete the proof.  

I often read `H10 was resolved by Davis-Putnam-Robinson and Matiyasevich' or sometimes they put all four names in alphabetical order. I like that--- it really was a joint effort.

3) She was inducted (a proof by induction?) into the National Academy of Sciences in 1975.

4) She was elected to be president of the American Math Society in 1982.  

5) She got a MacAuthor Fellowship prize in 1985 (Often called the MacAuthor Genius award.)

At the time it was worth $60,000.  Its now $625,000.

6) She also did work in Game Theory. Her paper An Iterative Method of Solving a Game, which is
here, is a proof from the book according to Paul Goldberg's comment on this post.

7) The Julia Robinson Math Festival is named in her honor (hmmm- is that a tautology?) Its purpose is to inspire K-12 students to get involved in math. For more on it see here.

8) (ADDED LATER) Commenter David Williamson pointed out that Julia Robinson did work on the transportation problem. See his comment and his pointer to the paper.

(ADDED LATER) When I hear Julia Robinson I think Hilbert's 10th problem.  I suspect many of you do the same. However, looking at items 6 and 8 above, one realizes that she did research in non-logic branches of math as well.