Fall Jobs Post 2024

In the fall, I write a jobs post predicting the upcoming CS faculty job market and giving suggestions and links. In the spring I used to crowdsource a list of where everyone got jobs but have since outsourced the crowdsource to Grigory Yaroslavtsev. Let's start with a few announcements.

FOCS in Chicago will have a Graduating Bits on Sunday, October 27 from 12-2 PM. If you have job openings for postdocs and researchers the FOCS organizers are collecting them here, The CATCS also maintains a Theoretical Computer Science Jobs posting site. You are also free to add pointers to theory-related job listings as comments to this post. More generally in CS, there is the CRA Database of Job Candidates and the CRA and ACM job postings.

MohammadTaghi Hajiaghayi is organizing a virtual theory jobs panel in November including yours truly. I'll post details here and on social media when it's finalized.

If you are a bit more senior, the Simons Institute is looking for a new director. 

Last year I suggested AI (which by the way just won two Nobel Prizes) wasn't dramatically affecting the CS faculty job market yet but

Many see programming, rightly or wrongly, as one of the first careers that AI will displace, which may reduce enrollment in the future, as offshoring fears drove CS enrollment down 20 years ago

It didn't take long. In two years we have gone from nearly all of our CS graduates getting jobs in the field to many of them struggling to get internships and jobs in the top companies if at all. If the past is any guide, a weak tech job market leads to fewer majors which leads to fewer slots for CS faculty. We'll start to see these trends this year and they will accelerate quickly if the tech jobs market doesn't recover.

Areas related to data such as Artificial Intelligence, Data Science and Cybersecurity, will draw the most interest. Best if you can tie your research to those areas, or at least that you are open to teaching in them.

Have a well-designed website with all your job materials and links to your papers. Make sure your Google Scholar, LinkedIn and GitHub (if relevant) sites are accurate and up to date. Make a short video describing your research to a general CS crowd. Take advantage of all the links above. Network at FOCS if you can make it. And start early. 

Emil Post Anticipated (more than anticipated) Godel and Turing

 (Thanks to James De Santis for pointing the article that inspired this post on Post. The article is pointed to in this post.)

What is Emil Post known for? I know of him for the following:

a) Post's Problem: Show that there is an r.e. set A that is strictly in between Decidable and Halt using Turing Reductions. He posed the problem in 1944. It was solved in 1956 by the priority method, simultaneously invented by Friedberg and Muchnik . (My students wondered who posted to the web first and if the other one could have seen it there.)

b) He invented Post Tag Systems, a natural problem that is undecidable. Or a model of computation. Depends on how you look at it.

c) The Kleene-Post Theorem which produces a set A that is strictly in between Decidable and Halt. It did not solve Post's Problem since A is not r.e. The proof used forcing and may have been the first or close to the first use of forcing. This was published in 1954.

In summary, I thought of Post as being a recursion theorist. 

 The more I read about Post the more I realize that calling him a recursion theorist is wrong but in an interesting way. Back in the 1950's  I am sure Emil Post was called a logician. The over-specialization that produces Recursion Theorists, Model Theorists, Set Theorists, Proof Theorist was about a decade away. In fact, people who worked in logic often also worked in other parts of math. (Post worked on Laplace Transforms. See The Post Inversion Formula as part of the Wikipedia entry on Laplace Transforms.)

I recently read the article, Emil Post and His Anticipation of Godel and Turing which shows that Post really did have some of the ideas of Godel and Turing at about the same time, and possibly before they did. I will discuss briefly what he did and why it is not better known; however, the article is worth reading for more on this.

What did Post Do? 

Part of Post's Thesis (1920) was showing that the Propositional Logic in Russell-Whitehead was consistent and complete. 

He tried to show that all of RW was consistent and complete. He got RW down to a normal form; however, he realized that rather than reducing the complexity he just localized it. In 1921 he noted the following (I quote the article).

a) Normal Systems can simulate any symbolic logic, indeed any mechanical system for proving theorems.

b) This means, however, that all such systems can be mechanically listed, and the diagonal argument  shows that the general problem of deciding whether a given theorem is produced by a given system is unsolvable.

c) It follows, in turn, that no consistent mechanical system can produce all theorems.

Wow- that sounds like the outline of a proof of Godel's Incompleteness theorem!

Why Didn't Post Publish This? 

 In 1921 Post suffered his first (of many) attacks of manic-depression. He was unable to get an academic job until 1935.  By the time he could have written a paper, his ideas were already known. Note that the items about Post I knew are all post-1940.

The Story is Interesting Because its Boring

There is no interesting conflicts between mathematicians in this story. No Newton vs Leibniz rap battle (see here) no plagiarism. Just bad timing and bad luck. So this story is not even worth  being exaggerated. 

But I find that interesting. Timing and Luck play a big role, perhaps bigger than is commonly thought.

Favorite Theorems: Gradient Descent

September Edition

Who thought the algorithm behind machine learning would have cool complexity implications?

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

John Fearnley, Paul Goldberg, Alexandros Hollender and Rahul Savani

Let's unpack these classes, subclasses of TFNP, where for every input we know there is an easily verifiable solution and we are looking at the complexity of finding it. PPAD is the class famous for having finding a Nash Equilibrium as a complete set, see this post for details.

PLS is the class of problems where we look for a local minimum. Finding a global minimum is NP-complete--think vertex cover. Finding a local minimum is often easier but still could be hard if you are optimizing over an exponential set of values.

CLS is a bit trickier to define, basically you are finding an approximate local minimum of a function mapping three real variables to one real value.

The authors show that gradient descent is complete for PPAD ∩ PLS even if you only use two input variables. Since gradient descent is in CLS, the equality follows. 

More in my 2021 post. On that post author Paul Goldberg commented

The paper is a fine example of the humorous stereotype of complexity theorists proving a problem "hard" when meanwhile the problem is being routinely solved in practice in the real world.

Nevertheless it's a neat complexity result and now officially one of my favorite theorems.