Would you be more productive if you didn't log on? It worked for Christopher Havens!

There are times when NOT having computer access (is that possible anymore?) can make you MORE productive. 

1) I did a lot of my Muffin Work when I was in Mexico for a bar matzah and had no computer access, and no Television in English (though Texas Walker Ranger, and Kindergarden Cop, were actually pretty good in Spanish even though I don't now Spanish.) 

2) I did work on NIM with Cash when I was stuck at an airport for 8 hours. 

3) I proofread (on paper!) most of my book with Erik D and Mohammad H when I was at a relatives house for four days  who had weak wifi and only got  ABC, NBC, CBS, PBS, some local channels, and COZI (not sure why they got COZI, though I am glad since I caught a good episode of Columbo).

4) Thanksgiving at my Mom's apartment (she's 93 years young!), with no computer,  I relearned the proof of the Hales-Jewitt theorem. I seem to learn/forget/learn/forget that one a lot. 

There are times when being AWAY from technology is helpful. I sometimes go to the Math Library and try to NOT use my cell phone. 

Having said that I do think that overall having access to papers online is great and that overall academic productivity has increased.  But there are times when the computer can distract you and time AWAY from it is good. 

Which brings us to the story of Christopher Havens. He works in Number Theory and logs on very rarely, perhaps never. He just works on math 10 hours a day. He has  a paper (with co-authors).  It take discipline to resist the urge to log on. How did he manage this?

He is in prison for murder.

Here is a podcast with him as a guest. 

Here is an article about him. 

Here is a math article where he is a co-author. 

Here is the short version of all of this: 

1) He is guilty of murder and in a max security prison in America.  It was a drug related shooting (why do people only talk about drug deals gone bad when they should also talk about drug deals gone good?) . When I first read Prison Inmate Solves Math Problem I thought that maybe a white collar criminal who majored in Math and was in a min security prison with access to the web (do white collar criminals have access to the web?)  But NO, Christopher Havens really did murder someone and is in max security.

2) He really has turned his life around. He really is not the person he was, and when he gets out I cannot imagine he will go back to drugs and crime. I suspect he will work on the Math Prison Project which I mention later. 

3) His mother says that when he was in High School (which is as far as he got for education)

he was helping students in math who were  2 grades above him, but he has no recollection of this.

4) When he was the hole (solitary confinement) someone who did Prison Education gave him (and others, he was not picked out) an envelope of math problems to work on--- pre-algebra. Christopher did them well and liked it and began requesting more advanced math books and learned math by himself, working 10 hours a day. When he requested a book it was random which ones he would get. I don't know why some were blocked. I don't think he knows why some were blocked. 

5) Some mathematicians from Italy (Italy?) contacted him and they began corresponding and yada-yada-yada, he has a paper now.

6) He has conceptualized the Math Prison Project to help other prisoners do math, though I would suspect not on the level he is on.  Then again, maybe the reason that P vs NP is still open is that we all have to many distractions, and conference deadlines, that a prisoner would not have. 

7) Some articles say that he solved a ancient problem in math that Euclid couldn't solve. This is not true. He helped solve some problems about continued fractions. 

8) There is going to be a movie about him, see here. I predict it will take an interesting story and make it less interesting and more fictional. 

What to make of all this? 

1) KUDOS to him!

2) I don't know which side of the nature/nurture argument this goes to

a) He OBVIOUSLY had math talent naturally or else he couldn't have learned all of that math.

b) He shows that HARD WORK and TENACITY can overcome other issue.

3) back to my original point- if you had the FREEDOM to work 10 hours a day JUST on math and had no other distractions, but also limited access to books and people,  would you be MORE productive? LESS productive? Also note- no faculty meetings, no teaching obligations, and no word processor to distract you. 

A Celebration of Juris

On November 4th I travelled to my undergraduate alma mater Cornell for a Celebration of the Life and Career of Juris Hartmanis who passed away in July. The workshop attracted many Cornell faculty and students, many of Hartmanis' former colleague and students, grad and undergrad, as well as his family. For the most part, the talks did not focus on technical content but rather memories of the great man. 

I talked about how Hartmanis founded the field of Computational Complexity and brought me into it. Herbert Lin told the story behind Computing the Future, a 1992 agenda for the future of computer science led by Hartmanis and the challenge to the report by John McCarthy, one of the founders of AI. Should the agenda of computer science be solely in the hands of academic computer scientists, or should it take into account its role in the larger scientific and world-wide community? We still face these questions today.

Ryan Williams gave a powerful talk about how Hartmanis personally intervened to ensure Ryan had a future in complexity. We are all better off for that.

After the workshop, Ryan and I walked around the campus and Collegetown reminiscing on how things have changed in the two decades since Ryan was an undergrad and the four decades (!) since I was. Most of the bars and restaurants have disappeared. The Arts quad is mostly the same, while the engineering building have been mostly rebuilt. There's a new computer science building with another on the way. 

I stayed in town to catch the Cornell football game the next day, as I once was on that field playing tuba for the marching band. They tore down the west stands to put up a parking lot and the east stands were sparsely filled watching Penn dominate the game.

Good bye Juris. You created a discipline, started one of the first CS departments, and plotted the future of both computational complexity and computer science as a whole. A master and commander indeed.

Fall Jobs Post 2022

In the fall I try to make my predictions on the faculty job market for the spring. The outlook this year is hazy as we have two forces pushing in opposite directions. 

Most of the largest tech companies are having layoffs and hiring freezes amidst a recession, higher expenses and a drop in revenue from cloud and advertising. Meanwhile computing has never had a more exciting (or scary) year of advances, particularly in generative AI. I can't remember such a dichotomy in the past. In the downturn after the 2008 financial crisis computing wasn't particularly exciting as the cloud, smart phones and machine learning were then just nascent technologies.

We'll probably have more competition in the academic job market as many new PhDs may decide to look at academic positions because of limited opportunities in large tech companies. We might even see a reverse migration from industry to academia from those who now might see universities as a safe haven.

What about the students? Will they still come in droves driven by the excitement in computing or get scared off by the downturn in the tech industry. They shouldn't worry--the market should turn around by the time they graduate and even today there are plenty of tech jobs in smaller and midsize tech companies as well as companies that deal with data, which is pretty much every company.

But perception matters more than reality. If students do stay away that might reduce pressure to grow CS departments.

Onto my usual advice. Give yourself a good virtual face. Have a well-designed web page with access to all your job materials and papers. Maintain your Google Scholar page. Add yourself to the CRA's CV database. Find a way to stand out, perhaps a short video describing your research. 

Best source for finding jobs are the ads from the CRA and the ACM. For theoretical computer science specific postdoc and faculty positions check out TCS Jobs and Theory Announcements. If you have jobs to announce, please post to the above and/or feel free to leave a comment on this post. Even if you don't see an ad for a specific school they may still be hiring, check out their website or email someone at the department. You'll never know if you don't ask.

Who first thought of the notion of Polynomial Time?

(Updated version of  Computational Intractability: A Guide to Algorithmic Lower Bound by Demaine-Gasarch-Hajiaghayi is here)

Any question like who first though of X is often hard to answer. I blogged about who first came up with the Fib numbers here. I've heard rumors that IBM had search engines way before Google but could not figure out how to make money off of it. There are other examples. 

I had learned that Cobham defined P in the paper The intrinsic computational difficulty of functions, in 1965. It was The conference on Logic, Methodology, and Philosophy of Science. The paper is here.  Jack Edmonds had the notion of P in the paper Paths, Trees, and Flowers here in 1965.

While it is true that Cobham defined P in that paper, and he might have been the first one to do so, was the notion somehow around earlier. I first thought the answer was no. Why?  Because if you look at Joe Kruskal's paper on MST  (see here) you don't see anything resembling time complexity. No O(E+Vlog V) or whatnot. So I thought that if the notion of  this algorithm runs in such-and-such time was not in the air, then certainly any notion of P could not have been. 

Hence I was surprised when I accidentally (more on that later) came across the following: 

In 1910 (really, 1910)  H.C.Pocklington analyzed two algorithms for solving quadratic congruences and noticed that 

one took time proportional to a power of the log of the modulus, where as

the other took time proportional to the modulus itself or its square root. 

THAT is the distinction between P and NOT-P. 

The paper is titled The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity. It appeared in 1910, in the Proceedings of the Cambridge Philosophical  Society, Volume 16, pages 1-5. (I could not find it online. If you know of a place online for it, leave a comment.) 

ADDED LATER: Here is the article in pieces: Page 1, Pages2,3, Pages4,5.

How did I come across this? And why had I NOT come across this in my roughly 40 years working in complexity theory? 

I came across it while reading a blog of Scotts, The Kolmogorov Option, see here where Pocklington is mentioned in passing. I am surprised how arbitrary the set of things ones knows can be. I have put the Pocklington story in the Demaine-Gasarch-Hajiaghayi book Computational Intractability: A Guide to Algorithmic Lower Bounds so that this knowledge gets to be better known.

ADDED LATER: That Cobham and Edmonds are known for discovering or inventing P is an example of  the well known 

Columbus Principle: Things are named after the LAST person to discover them (note that Columbus was the last person to discover America.)

Bonus Question: Most principles where the author is not on it, the author might be unknown. NOT in this case. I KNOW who coined the term `Columbus Principle' Do you? (It was not me.) 

The Structure of Data and Machine Learning

Terry Tao entitled his 2006 Fields Medal Lecture "The Dichotomy between structure and randomness" and state the Structure Theorem: Every object is a superposition of structured object and a pseudorandom error. He gave many examples and how he used these results to prove (with Ben Green) that the primes contain arbitrarily long linear progressions.

There is a nice Kolmogorov interpretation. Recall K(x) is the smallest program that produces the string x. For a finite set S, K(S) is the smallest program that recognizes membership in S. For a string x, take the largest set S containing x such that K(x) is close to K(S) + log(|S|). S is the structure and x is a random element of S. Vereshchagin and Vitanyi have a nice paper on this topic.

Machine learning aims to discover the set S from a set of examples x. This is why I think of P = NP giving us an ideal machine learning algorithms--use P = NP to find a circuit that describes S for a time-bounded version of Kolmogorov complexity. Recent tools in machine learning seem to find this S without needing the full power of P = NP.

Consider languages where German or Japanese is a random example of a "natural language". Linguistics tries to understand the structure of natural languages. Recent ML translations algorithms use that structure (without understanding it) to translate between pairs of languages. 

How about generative AI? Diffusion methods create a set S of all reasonable images by turning images into random noise. To create images it reverses that process, starting with random noise to create random elements of S. Prompts just add conditions to the process.

I read the Vereschagin-Vitanyi paper back in 2004 and the Kolmogorov structure model goes back to the 1970s. Finding the structure seemed intractable for any interesting application. Now that ML is proving this wrong, the world is a different place.

Euclidean TSP is NP-hard but not known to be in NP. Why not known?

BILL: Lance, I was looking into TSP, metric TSP, Euclidean TSP since I am going to teach about P, NP, NPC, and approximating NPC problems and I came across the following from Lipton's book The P=NP Question and Godel's Letter (I paraphrase):

Graham proved that Euclidean TSP was NP-hard. But it is open if it is in NP. The difficulty hinges on a beautiful problem that is still open over thirty years later: Can we tell, given naturals a1,...,an,k if

\sqrt{a1} + ... + \sqrt{an} \le k

What I want to know is, is it still open? Lipton's book was written in 2010, so that was. uh, uh...

LANCE: 11 years ago.

BILL:  Which is a long time ago- so has it been cracked?

LANCE: No it has not. And, by the way, I blogged on it in 2003.

This raises some questions:

1) Is  the sqrt problem above in P? NP? (I have seen it stated that the problem is in PSPACE.) 

2) Where do people think the problem is?

3) Why is it still open? Some options (I am sure there are more.)

a) Not that many people are working on it. But if not, why not?

b) The problem is just dang hard! That's probably why P vs NP is still unsolved and why FLT took so long, and why my proof of the Riemann hypothesis was so long in coming.) I am reminded of Erdos' quote on The Collatz Conjecture: Mathematics may not be ready for such problems. And you all know what Erdos said about R(5). 

c) Reasons a and b above may lead to a death spiral: People THINK its hard so they don't work on it, then since nobody works on it no progress is made, reinforcing that its hard. 

Should you quit Twitter and Texas?

Generally with some exceptions, I use Facebook for personal stuff, LinkedIn for Illinois Tech stuff and Twitter and this blog for CS stuff. Many of you got to this post through the Twitter link. Now that Elon Musk has bought the social media company, should I and the rest of the academic twitterverse move on to something else?

I'd say not yet. Let's see what Elon does to the place. Maybe he can allow more points of view, without turning it into a cesspool. Or maybe he ruins it. It'll be a network effect--if too many academics leave Twitter, I'd have to follow or I'd have few followers. I wonder where they will go. I hope it isn't TikTok.

On a similar vein, I often here of those who suggest we don't hold conferences in certain jurisdictions for political reasons, for example Texas, because of its laws against abortion and transgender rights. I don't believe computer science, as a field, should be making decisions based on politics. Academics who live in these states don't generally hold the same views as the political leaders in those states.

Should we not have meetings in Illinois because some in our field might be opposed to abortion? Or do we just assume everyone has the same political views in the field. Individuals can make their own choices as to whether to attend, but it's best when politics is left out of academics. FOCS 2022 is wrapping up today in Denver. Seems like a safe choice--perhaps all US conferences in the future should be in Colorado. 

There are limits--I wouldn't attend or organize a conference in Russia in the near future. But if we start eliminating locations based on politics, we'll only be able to meet up in the metaverse, and we won't have social media to tell us how to get there.