ChatGPT tried to write an obit for Martin Davis. What it got right, wrong, and what to make of it.

When Martin Davis passed away Lance emailed me what he got from using ChatGPT to do an obit. Here it is and I also note what it got wrong.

-------------------------------------------------------------------------

Born in 1928 in Brooklyn, New York, Davis received his bachelor's degree from Brooklyn College in 1950 [WRONG-1948] and his Ph.D. from the University of Chicago in 1953 [WRONG- it was Princeton in 1950].  He went on to have a distinguished career, with positions at the Institute for Advanced Study, the University of California, Berkeley, and New York University, where he spent the majority of his career.

Davis made significant contributions to the field of mathematics, particularly in the areas of computational complexity theory, recursive function theory, and mathematical logic. His work on the Davis-Putnam-Robinson-Matiyasevich algorithm [ADDED LATER BASED ON A COMMENT: WRONG-The DPRM theorem is that there is NO algorithm. It is not an algorithm.] helped establish the connection between logic and computers [WRONG- THE CONNECTION BETWEEN LOGIC AND COMPUTERS WAS ALREADY WELL KNOWN. CONNECTION BETWEEN COMPUTABILITY AND POLYNOMIALS WOULD HAVE BEEN BETTER] and has had major implications for the field of computer science.

In addition to his academic pursuits, Davis was also a dedicated teacher and mentor. He was a popular and engaging speaker, known for his wit and clarity in explaining complex mathematical concepts. He inspired and encouraged countless students throughout his career and left a lasting impact on the mathematical community.

Davis was the recipient of many prestigious awards and honors, including the ACM Turing Award [WRONG- DAVIS NEVER WON A TURING AWARD], the highest honor in computer science, in 1994. He was also a member of the National Academy of Sciences and the American Academy of Arts and Sciences.  [I WAS ABLE TO VERIFY THAT HE WAS IN THE AMERICAN ACAD. I WAS NOT ABLE TO VERIFY THAT HE WAS IN THE NATIONAL ACAD, BUT I DO NOT KNOW.]

Martin Davis will be greatly missed by his colleagues, students, and friends.  His contributions to mathematics and computer science will not be forgotten and will continue to inspire future generations of mathematicians and scientists.

-------------------------------------------------------------------------

This raises some questions

a) It got some factual things wrong. This surprised me. Its also a cautionary note: when you using ChatGPT for a first draft you need to check factual information. 

b) I was going to take the obit and modify it for my post. I found that I could not do this, not because of the mistakes in it, but because its not what I wanted to emphasize. See my obit post here.

c) Will this make bloggers jobs  and other jobs easier by just posting modified versions of things ChatGPT outputs? This is both a hope (less work) and a fear (no work). Options: 

c1) Much like farming, there will be a transition period where people are out of work but in the long term its a good thing that instead of 90% of people working on farms its 3%. So people transitioned (or the next generation did) to other jobs. (One could argue if this is really a good thing, though I've heard farming was VERY HARD WORK so people are happier not being farmers.)

c2) The jobs that are going away, there will NOT be replacement jobs and we are looking at an economic and psychological catastrophe. 

d) Even before ChatGPT I had heard of using a program to output a sports story about little league games for very local papers. 

e) The obvious fear: will students have ChatGPT produce their papers for them? In its current state the students would have to modify the paper. A few ways this could go:

e1) Analog to calculators: Students used to have to memorize multiplication up to 20x20 but now we let t hem use calculators. Students used to have to write papers, now we let them use ChatGPT and modify. This may be forced on us as opposed to something we want to do.

e2) There will be a fierce fight where teachers what students to NOT use ChatGPT but its hard to stop them. 

e3) ChatGPT will get much better. Even so, there will still be some things its bad at. Students won't know which is which, or won't care.

e4) I am tempted to say it won't affect math but I think it might for, say, standard proofs by induction, standard calculations from calculus (we already have programs that can differentiate and integrate- has that affected how Calculus is taught or graded?). 

Semantic Search for the Blog

 As Google started to limit academic storage, I started looking at Google Takeout and started wondering what I could do with all that data. I downloaded all the posts from the blog, since we use Google's blogger, and ran them through OpenAI's Ada Embedding. The Ada embedding maps text up to 8192 words into a point on the 1536-dimensional unit sphere. You can measure the similarity between two embeddings via a simple dot product, giving you the cosine of the angle between them.

So I created a semantic search for the blog. Go ahead and try it out.

Search for  

You can enter a search term, phrase, or the full URL (including https) of a blog post. It will return a list of the 5 closest posts, with the percentage match, computed as the square of the cosine. I don't have a mechanism for automatically updating the files, so you'll only see posts from 2022 and earlier.

This was an Open AI-assisted affair, as I used ChatGPT and GitHub co-pilot to help with the python and pandas data frames. It took me longer to figure out how to create a web application so you can try the search. Similarity match doesn't work like normal searches, for example if you search for a city like "Detroit", you'll get posts that mention other cities. Some other oddities, like "mad" seems to match "Madhu". It probably says something about me that my most happy post is not about some great new theorem but about baseball.

Martin Davis Passed Away on Jan 1, 2023

As you probably already know from other sources, Martin Davis passed away on Jan 1, 2023, at the age of 94. His wife Virginia died a few hours later.

He majored in math at Brooklyn College and graduated in 1948.

He got his PhD under Alonzo Church at the Princeton in 1950.

Two years for a PhD seems fast!

His Phd was on Recursion theory.

In it he conjectured that Hilbert's tenth problem (below) is undecidable.

He is known for the following (if you know more, please leave a comment).

1) Hilbert's Tenth Problem.

Hilbert posed 23 problems in the year 1900 for mathematicians to work on

over the next 100 years. Hilbert's tenth problem, in modern terminology, was

Find an algorithm that will, given a polynomial p \in Z[x_1,...,x_n],

determine it has a Diophantine solution (that is, a_1,...,a_n\in Z

such that  p(a_1,...,a_n)=0).

 In Hilbert's article he did say in a preface to all of the problems. Here is the exact quote:

Occasionally it happens that we seek the solution under insufficient hypotheses or in an incorrect sense, and for this reason do not succeed. The problem then arises: to show the impossibility of the solution under the given hypotheses or in the sense contemplated.

Hilbert had hoped that this problem would lead to deep results in number theory. And it has to some extend. However this went from being a problem in number theory to a problem in logic. That might not be quite right: the result did use number theory.

In 1961 Davis-Putnam-Robinson showed that the problem is undecidable IF you also allow exponentials.  This may have been a turning point for the conventional wisdom to shift from `Probably Solvable' to `Probably Unsolvable.'

Martin Davis predicted that the H10 would be shown undecidable by a young Russian by the end of the decade. He was correct. Yuri Matiyasevich did indeed prove H10 undecidable in 1970. By all account Davis was delighted. When the result is cited usually all four people are credited which is as it should be.  He wrote an excellent exposition of the complete proof from soup to nuts in: 

Hilbert's tenth problem is unsolvable, American Math Monthly, Volume 80, No 4, 233-269.

When I first heard of this result I assumed that the number of variables and the degree to get undecidability was huge. I was wrong.  I wrote a survey of H10 emphasizing what happens if you bound the degree and the number of variables, see here

2) SAT Solvers. Davis-Putnam-Logemann-Loveland outlined a SAT Solver, or really a class os SAT Solvers. While I doubt it was the first SAT Solver, it was an early one that tried to cut down on the time needed.

3) He wrote the following books:

Computability and Unsolvability (1958, reprinted 1982)

Applied Non-Standard Analysis (1977, reprinted 2014)

Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science (1994 (with Elaine Weyuker)

The Universal Computer: The Road from Leibniz to Turing (2000, reprinted as

Engines of Logic: Mathematicians and the origin of the computer)

The Undecidable: Basic Paper on undecidable propositions, unsolvable problems and computable functions (2004)

4) He was a recursion theorist who could actually program a Turing Machine to really do things. There are still some people who do that- getting the UTM down to a small number of states, and the work (the Wolfram Challenge), and the Busy Beaver Function (see Scott Aaronson's open problems column here,

but I think this is done less by academic recursion theorists than it used to be. I do not have my students in Automata Theory write any TM code. Clyde Kruskal, who had that same course from Martin Davis, thinks that I should. 

4) For more on Martin Davis see this obit here and/or his Wikipedia page here

Positional Encoding

Given the excitement over ChatGPT, I spent part of the winter recess trying to understand the underlying technology of Transformers. After trying various tutorials, I found the best explanation comes in the original 2017 paper, Attention is All you Need. This is my attempt to figure out positional encoding in transformers with some naive questions. Let me know if I'm completely off base.

Earlier models like Recurrent Neural Nets and Convolutional NNs worked under the assumption that information close by was more likely to be correlated. Machine learning seems to improve as the models make fewer and fewer assumptions about the data and transformers use positional data with no predisposed favoritism to nearby inputs.

The attention paper uses the following encoding for positions. Let α(j) = 10000^-j/d where d is the dimension of the input embedding, i.e. the number of numbers used to represent each word of the input. We encode position p as d/2 pairs of numbers cos(p α(j)) and sin(p α(j)), for j ranging from 1 to d/2. They chose this function because relative positions are easy to address. We can address a relative position of a fixed k by a linear combination of cos(p α(j)) and sin(p α(j)) using the addition rules of cos and sin.

cos ((p+k) α(j)) = cos(k α(j)) cos(p α(j))  - sin(k α(j)) sin(p α(j)) 

sin ((p+k) α(j)) = cos(k α(j)) sin(p α(j))  + sin(k α(j)) cos(p α(j)) 

The d-dimensional vector of position encodings is added to the input embedding.

Why is the position encodings added to the input embedding?

I scoured the Internet and can't seem to find a good reason for this, other than it seems to work. Wouldn't the linear combinations to handle relative positions muddle up the input embedding? Since the input embedding is learned, perhaps some parts of the embedding are made zero or very small so the positional embedding stands out. Why not concatenate the two, have separate inputs for the input embedding and the positions? You wouldn't need to fully double the dimension since you would no longer need to match the dimension of the input encoding.

Why not use complex numbers?

I see cos(p α(j)) and sin(p α(j)) and immediately think of them as the real and imaginary parts of e^{p α(j) i}. So why not just do the positional encodings as complex numbers? This paper suggests multiplying e^{p α(j) i} with the input embedding, i.e., the input is embedding into the amplitude and the position by the phase. That makes more sense. You can now multiply by e^{p α(k) i} to get the relative position j+k without affecting the input embedding.

I don't see a good reason not to use complex numbers for transformers, given that most learning packages and GPUs can handle complex numbers just fine. Even if you don't want to use complex numbers you could multiply the sin and cos versions of the positional encoding instead of adding to achieve a similar effect.

How about positional encoding for outputs?

Transformers output words in order but that makes it harder to relate outputs that are far apart. So why not give positional encoding to the outputs. A post-processor could then put the outputs in the correct order. More generally, how about outputting a program that produces the real output? We know transformers can generate code, and this way can handle operations that transformers normally struggle with, like multiplication or sorting.

Complexity Year in Review 2022

Complexity result of the year goes to

NP-Hardness of Learning Programs and Partial MCSP

by Shuichi Hirahara

Consider the following version of Occam's Razor: find the smallest program consistent with your data. Hirahara shows that solving this problem is randomly hard for NP. The paper also takes a major step to understanding the complexity of the Minimum Circuit Size Problem, a major area of study in computational complexity over the past few years.

Runner up goes to Maximum Flow and Minimum-Cost Flow in Almost-Linear Time by Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg and Sushant Sachdeva. The title speaks for itself.

In the computing world, 2022 has become the year of machine learning taking over. It seemed like almost every week we saw a new ML breakthrough from AlphaTensor, improving on Strassen, to AlphaFold mapping out the structure of nearly every known protein. AI generating new text, pictures and code and playing Diplomacy. Not to mention ChatGPT that will disrupt education and everything else. Enough to almost make us forget the tech layoffs and the downfall of Twitter as we know it.

We remember Fred Brooks, Juris Hartmanis, Joel Moses, Rolf Niedermeier, Alexander Vardy, Gerhard Woeginger and Fastlane.

Thanks to our guest posters Boaz Barak, David and Tomas Harris, Jonathan Katz, David Marcus, Jelani Nelson, Prahalad Rajkumar and Aravind Srinivasan.

Bill and I wish you the best for the holidays and look forward to keeping you informed and entertained with minimal AI assistance. 

Voter Suppression, Harvard Style

The following appeared on Harry Lewis's blog, here, hence it is written in his voice, though it is a co-authored. You'll see why later.  I then have some comments on it. 

------------------------------------------

Voter Suppression, Harvard-Style

(This piece is jointly authored by Harry Lewis (Harvard) and Bill Gasarch

(University of Maryland at College Park). Harry was Bill's PhD Advisor.)

There are elections in Hong Kong, but to get on the ballot you have to be nominated by a committee controlled by Beijing government.

Elections for the Harvard Board of Overseers—one of Harvard’s two governing bodies—are almost as well-controlled. A Harvard Alumni Association (HAA) nominating committee curates a slate of candidates, from which alumni make their selections.

But an alternative route to get on the Harvard ballot exists, at least in theory. So-called “petition” candidates have always been rare—but after several climate activists were elected in 2020, the rules were changed to make it even harder. Among other things, the number of petitions to get on the ballot was raised by a factor of fifteen, to more than three thousand.

This year, noted civil libertarian Harvey Silverglate, concerned about freedom of expression at Harvard, is trying to make it onto the ballot.

The authors are computer scientists. We are neither technologically naïve nor afraid of computers. Harry has long been concerned about issues of student freedom and Harvard governance, and suggested to Bill, Harry’s sometime PhD student, that he sign Silverglate’s petition. This is an account of Bill’s trip through the resulting electronic purgatory.

To add your name, you have to fill out a web form. To access the web form, you need a HarvardKey. To get a HarvardKey, you have to fill out another web form. So far, so good.

The HarvardKey web form wanted Bill’s 10-digit HAA ID, which he was told to find on the address sticker of his copy of a recent Harvard Magazine (sent to all alumni). Bill had one handy, so he looked and found … a 9-digit number. He tried entering that number—no luck. He noticed it began with three 0s, and tried adding a fourth—that did not work either.

The web form had a number to call. Someone answered, and said some information would be needed before dealing with digits. Name (fine). Year of degree (fine). MIDDLE name (well, fine, though no one but Bill’s mother ever used it, and only when indignant). Date of birth (well, OK, but now we’re getting into territory we don’t casually reveal any more). When he got his MASTER’s degree. Bill did not know—that’s just something Harvard gives en route to the PhD. Turned out he actually didn’t need to know, an estimate was good enough. The person on the phone gave him his HAA ID, which bore no relation to the number on his address sticker.

Let’s pause there. Some people never call tech support because they have never found it helpful to do so. Any such person with a 9-digit address sticker number could not participate in the petition process.

Bill entered his HAA ID and received an error message saying that … KEY-5003 was missing. Happily, Bill had kept the support person on the phone (this was not his first rodeo).

Missing KEY-5003 turned out to mean that Harvard did not have his email address. He supplied it and was told he would get an email confirmation later in the day.

He did get an email later in the day. It listed eleven steps to claim his HarvardKey. Step 6 was to wait for a confirming email (he thought this WAS the confirming email), but after step 5 the system told him he was not in the system and it could not continue.

Another call to a support line. No, Bill was told, he has to wait 24 hours to get his email address updated, and would not get a confirming email. Just try tomorrow. Like the email said. Except that it didn’t say that, nor had the person he spoke to on the previous call.

Bill waited 24 hours and tried again, and got a little further through the eleven steps—and then was told to wait ANOTHER 24 hours for the account to activate.

24 hours later he tried again, from home, and failed again. Then he went to his office and succeeded—no clue why.

Now finally he got to the petition, which required Bill’s graduation year—and Silverglate’s­­, which Bill found but shouldn’t have been needed since this petition was specific to Silverglate.

Three days and two phone calls to sign the petition. To be fair, the people Bill spoke to on the phone were kind and helpful. Probably they themselves were struggling with the systems.

And we knew already that HAA is technologically challenged. A few weeks ago, it abruptly announced that it could no longer handle email forwarding. After alumni blowback, it just as abruptly announced that it would NOT end its forwarding service—oddly, while cautioning that the service was unlikely ever to work very well.

When election officials want to suppress the vote somewhere, they under-resource the voting process, forcing voters to cross town and wait in long lines. What happened to Bill is so comical that it is hard to imagine that the specifics were intentional. On the other hand, under-resourcing the petitioning process, allowing it to be so defective, misinformed, and hard to use that many people won’t exercise their franchise—isn’t that a form of voter suppression?

Why not be true to Harvard’s motto, Veritas, and just post on the web, For the alumni to choose the Overseers is an anachronism. Today’s alumni voters can’t be trusted to do it wisely. Since we can’t get rid of this system, we are going to make it all but impossible to nominate by petition. Try if you wish, but if you do, abandon all hope, ye who enter here.

-------------------------

I originally emailed Harry what I had to do to sign the petition with my point being

`Yes, I am a luddite but that has NOTHING TO DO with why I am having a problem.''

(I had meant to do a blog on that topic. I may still.)

Harry saw this for what it was- Voter Suppression. He wrote the Op-Ed using my story and made me a co-author. (We have never published together so it amused me that our first pub together would be 37 years after he was my advisor- perhaps a record. Does having a joint blog post count?) What is above is basically that Op-Ed (I think the version Harry submitted omitted that my mom is the only one who uses my middle name.) 

He submitted this as an Op-Ed to three places sequentially. 

1) The New York Times turned us down (not a surprise) by not even acknowledging it had been submitted (really?).

2) The Boston Globe turned us down (a surprise).

3) The Harvard Crimson turned us down (a shock!).

Voter Suppression followed by censorship.

AND back to the original issue: Harvey does not have enough people on the petition yet. I urge you to READ Harry Lewis's post on Harvey here and IF you are a Harvard Alumni AND you agree that Harvey would be a good overseer THEN sign the petition. Or at least try.

FinTech is Dead, Long Live FinTech

Bill didn't feel he had the expertise to share new insights on the FTX affair. Never stopped me.

FTX is nothing short of corporate malfeasance in a poorly regulated industry, and since Bill had posted, Sam Bankman-Fried was arrested and charged with fraud and conspiracy. The whole affair has rippled through the cryptocurrency ecosphere and will likely lead to a much higher regulatory framework than the industry was hoping for.

Cryptocurrencies have had an interesting 2022 starting with the Superbowl ads Bill was rallying against. FTX even sponsored baseball umpires, sports arenas and fortune cookies including this prescient one

Those were in the glory times of FinTech, i.e. early 2022. Even before FTX had its problems, we had the Three Arrows Capital bankruptcy and the TerraUSD stablecoin collapse. Bitcoin lost over 60% of its value during the year. 

Of all the problems we've seen with cryptocurrency, it's never because of the crypto. I'm still shocked how the person or people called Satoshi Nakamoto got it mostly right on the first try. They did fail to account for the energy needed to mine bitcoin once bitcoin became valuable, but on the other hand who could have predicted bitcoin would become so valuable. Certainly not me.

I still don't see much of a market for most cryptocurrencies beyond speculation and illegal activities, though we have much of both. Nevertheless it feels weird in 2022 that we still use physical bills and coins. I am hopeful for a CBDC (Central Bank Digital Currency), not a stablecoin tied to a dollar, but US currency itself just in digital form.

We now use digital tickets for most events and transport. Even driver's licenses and passports are moving digital--they only gets scanned anyway. There are a few remaining uses of paper--property titles, legal wills, social security cards, birth, death, marriage and divorce certificates. Perhaps we could use blockchain or even centralized databases to eliminate these as well.

Blockchain could also be helpful to track our digital goods, so we can use the music, movies, books, games, virtual clothes and accoutrements on different platforms without having to buy them twice. (HT Siva)

The most important use of FinTech will be for those who have the least, those who pay large fees to have a bank account, cash a paycheck or send money to family overseas. FinTech can be a great democratizing tool, if we use it that way and not just as another get rich scheme.

Commercials are not logical. FTX edition.

Some people asked me to comment on FTX since I teach Cryptography. My insights are no better than anyone else's; however, I have wanted to do a blog post about the illogic of commercials, so I will do that with FTX as an example. 

All conversations in the post are fictional.

------------------------------------

Alice: Bob, why did you invest $1,000,000 with FTX?

Bob: Because Tom Brady endorsed it. (See here for an article about that and here for a commercial Tom Brady did for FTX.) 

Alice: But Tom Brady is a football player, not a finance person. 

Bob: Well... I know that now. 

(For an absolutely fantastic---and now ironic---commercial for FTX , see here.)

------------------------------------------------------------

The people in commercials are paid to hawk the product. 

a) Are they experts? In the above case, about FTX,  NO, they are not. So the commercial should not convince anyone to buy the product. 

b) There are commercials where the people are experts. For example, a basketball player endorsing a sneaker brand (not quite an expert, but they do use the product). But even this should not work since the viewers KNOW that the person is being PAID to tell us it's a good product. 

c) Commercial spokespeople (Geico's Gecko, Progressive's Flo, Dos Equis---the world's most interesting man, see his commercial here and a Ramsey Meme based on it here) are even stranger- they are fictional characters who are urging me to buy something.  So the question "Are they experts?'' doesn't even make sense. Someone pretending to be someone else is also pretending to like a product they do not use. 

d) Some commercials pretend to be  informative but are not. For example, the insurance companies seem to brag about something that ALL of the insurance companies do such as bundling or not-paying-for-what-you-don't-need.

e) A truly new product may have an informative commercial, just to tell me that it's out there. For example, Stephen Colbert's Americone Dream Ice Cream,  which is awesome. (My spellchecker thinks Americone is not a word. This time they are probably right.) 

f) SO, if I did a commercial for Stephen Colbert's Americone Dream Ice Cream would you try it? Let's say I wasn't being paid and I truly did it for my love of that ice cream. This  STILL doesn't make sense--- my tastes and yours may differ. However, you can try it, and decide, and  it costs far less than $1,000,000.

---------------------------------------

So what are we left with? The only commercials that make logical sense would be those where 

a) the person is an expert,

b) the person is not being paid,

c) the person is telling you something about the product that distinguishes it from its competitors OR  it's a new product, and

d) it's not a matter of taste---there is an absolute standard that is easily understood. 

Do you know of ANY commercials like that? Influencers who are NOT paid by the people whose product they are hawking (are there such influencers?) might begin to qualify. 

------------------------------------------------------

So LOGICALLY commercials should not work. So why do they?

a) They don't. It's possible they just aren't that effective. See here for "DON"T WORK'' and here for 8 times when it did work. I think this is a great commercial (watch it to the end) but it does not make me want to go out and buy soup. (Stan Freberg wrote some GREAT commercials. They are on YouTube and I recommend them highly for entertainment. He also has several great novelty-song albums.) 

b) Indirectly. They build brand awareness.

c) Because people are stupid. This is not an interesting answer since I still want to know what their reasoning is, whether or not it's faulty.

d) Because you are part of a movement. Drink the Uncola (7UP) to be rebellious! Or the 1984-Apple commercial (see here). These are both odd since drinking 7UP or having an Apple Computer seem to me to be the opposite of rebellious. 

e) Buying the product to express your philosophy: 

Ted: Carol, why did you invest $1,000,000 in FTX? 

Carol: Because I believe in effective altruism.

Ted: Do you still?

Carol: This might need a rethink. But for now I'll  invest by getting a Freedom Unlimited credit card that gets cash back since Kevin Hart says I should (see here).

Harry Lewis's talk on The Birth of Binary on Dec 8 (Thats today!)

 (Added Later: the talk is now available: here. When I tried it it said I did not have permission

but I got it to work anyway.) 

More on the information on Harry Lewis's  talk is in his blog post about it:here

1) On Dec 8, 2022 Harry Lewis is giving the annual Thoraf Skolem Memorial Lecture on

                                                     The Birth of binary 

Its in Oslo. BOO- I can't get there!

It will be on Zoom- YEAH I can see it! Here is the link: here

It will be at 7:15AM East Coast Time- BOO- I needs my sleep!

(Plus, I am posting this after its over)

It will be recorded-YEAH I can see it later. CAVEAT- Will I?

(It will be linked to at the link in item 4 below.)

2) Lloyd Strickland and Harry Lewis have a book on the subject: here titled

                               Leibniz on binary: The Invention of Computer Arithmetic.

3) Questions like who invented binary  or who invented parallelism or who first proved the dual-muffin theorem can be hard to answer. First  is an ill defined term. In the current era we can see who published first, which is usually well defined, though might not get at the heart of the issue.

Which brings us to Leibniz on Binary.  He had lots of notes, not really intended for modern readers or even for readers in his own time. The notes lay out binary notation and some algorithms, but not in a modern way. Hence the book is quite valuable to tell a modern audience what Leibniz did. Leibniz published very little of it.  Even so, seeing what he did, the statement

                                             Leibnitz invented binary

is reasonable. Some of his notes dealt with what we would now call complexity, so I need to add him to my already-long list of people who had modern ideas about complexity. 

4) For more on the Skolem Lecture, see here

The Future of Education is Personal

 

With all the excitement about ChatGPT, how will machine learning disrupt education, say five to ten years down the road?

My guess: individualized tutors. Imagine a tutor working with you teaching you important concepts, walking you through examples, answering your questions, going at your own pace, like the Oxford system. The Oxford tutor system doesn't scale well, or at least it wouldn't if we have human tutors. But we can scale using machine learning and we're not far away from being able to do so. Such tutors will be infinitely patient, have full knowledge of all written material, speak in any language with any voice and personality.

You can "meet" with your tutor in many different ways, from a deep fake video chat or with augmented or virtual reality to have a tutor in the room with you, or perhaps a physical robot, neural implant or something we haven't even though of yet. In poorer countries you can get tutored with something as simple as text messages on a cell phone. 

A tutor can take on any form. You could get tutored by fictional characters such as Yoda, Darth Vader or Miss Frizzle. ML can capture the personality of real people--imaging a course about Kurt Vonnegut taught by the author, government from Henry Kissinger or a course in quantum computing from your own personal Scott Aaronson. But most importantly you can have a tutor who looks and sounds like you, with your own language, gender, race and ethnicity.

Somehow we'll have to find ways to include the social aspects such as working in groups, socializing, playing sports and living together. But that one-one-one teaching experience that most of us cannot afford  today will be cheaply available tomorrow.

And what will this all mean for teachers, professors and universities? A good question for future blog posts.

How do we keep the community connected?

A colleague said how they enjoyed watching the collapse of Twitter under Elon Musk. But I use Twitter to keep connected to the CS community. In Twitter I hear not only new results but ones that excite particular people. I watch the debate between those who see ML as revolutionary and those who see ML as revolting. I see the issues that our community worries about and those that they celebrate. I follow people as they progress in their careers or outright change them. Mostly it just makes me feel part of an academic community that goes beyond my own institution. 

A bit surprisingly, so far Twitter hasn't collapsed. But it could and I expect many of my followers and those I follow spend less time there. I set up a Mastodon account @fortnow@fediscience.org but not much happens over there, though feel free to tell me who I should be following. There are many other social networks but none that bring us as a field together.

Blog posts and their comments play a role but not like they used to. There's CS Theory StackExchange which has some good (and not so good) technical discussions but we don't really have conversations there. 

How about conferences now that researchers are (mostly) willing to attend in person? Since conferences in CS are the primary publication venue, we have too many meetings and many won't go, or at least won't go in person, if they don't have a paper in the conference.

So, once again, I suggest a big theory conference we hold every four years that everyone who's anyone will make sure to attend. Hey, it works for the World Cup. 

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.

What was the recent Nobel Prize in Physics really about?(Guest Post)

 David Marcus was a Math major a year ahead of me at SUNY Stony brook (he graduated in 1979,

I graduated in 1980). He then got a PhD from MIT in Math, and is a reader of this blog.  Recently he emailed me that he thinks the current Nobel Prize Winners in Physics do not understand their own work. Is it true? Let's find out!

------------------------

(Guest blog from David Marcus)

2022 Nobel Prize in Physics Awarded for Experiments that Demonstrate Nonlocality

The 2022 Nobel Prize in Physics was recently awarded to experimenters who demonstrated that the world is nonlocal. The curious thing is that neither the writers of the Nobel Prize press release nor the recipients seem to understand that this is what they demonstrated.

For example, the press release (see here) says: "John Clauser developed John Bell's ideas, leading to a practical experiment. When he took the measurements, they supported quantum mechanics by clearly violating a Bell inequality. This means that quantum mechanics cannot be replaced by a theory that uses hidden variables." That is not what the experiments mean, and the statement is false.

The word "locality" means that doing something here cannot instantly change something other there.

The experimental setup is the following: You prepare two particles, A and B, and send them in opposite directions so that they are far apart. You and your colleague do experiments on each particle at the same time. If you and your colleague perform the same experiment, then, from your experiment on A, you can predict with certainty the result of your colleague's experiment on B (and vice versa).

In a paper in 1935, Einstein, Podolsky, and Rosen pointed out that, assuming locality, the experimental results at A and B must be determined by the source that prepared the particles. They didn't actually say, "assuming locality", but they implicitly assumed it. (If you disagree with them, please offer an alternative.)

In 1964, John Bell published his paper. In it, he considered three of the experiments that could be done on the particles A and B. Assuming the results are determined by the source (which follows from Einstein, Podolsky, and Rosen's argument), he derived an inequality on the correlations between the results of the three experiments on the two particles. The math is simple; for details, see here.

The Nobel Prize winners did experiments, and their results violated Bell's inequality (or similar inequalities). Hence, the world is nonlocal.

The simplest theory that agrees with experiment is Bohmian Mechanics. This is a deterministic theory of particles whose motion is governed by a wave (the wave function being the solution of the Schrödinger equation). Of course, Bohmian Mechanics is nonlocal, as is the world.

The Media Coverage of the Matrix result is Terrible (though not worse than usual)

 BILL: A computer program (or an AI or an ML or whatever) found a BETTER way to do matrix mult! Its in the same spirit as Strassen. I've always wondered if Strassen was practical  since it is simple, and computers have come a long way since 1969, though I suspect not (I WAS WRONG ABOUT THAT). I'll blog about and ask if Strassen will ever be used/practical   (I did that post here).

READERS: Uh, Bill,  (1) Strassen IS used and practical and (2) the new algorithm only works in  GF(2). (Lance did a post about the new algorithm where he makes this explicit here.) Some readers claimed it was GF(2^k) and some that it was fields if char 2. In any case NO it is not a general algorithm.

BILL: There is good news and what others might consider bad news but I do not.

GOOD NEWS: I learned that Strassen IS practical and used, which I did not know. 

GOOD NEWS: I learned that I was WRONG about the new algorithm since I just assumed it worked in general, and updated the post so others would not be deceived. 

BAD NEWS: Darling asked if I was embarrassed to be wrong. If I am embarrassed that easily I would have quit blogging in 2009. 

DARLING: So Bill, how did you get it so wrong?

BILL: Well obviously my bad for not doing my due diligence. But that's not what's interesting. What's interesting is that if you read the articles about it for the popular press you would have NO IDEA that it only works for mod 2. Its like reading that quantum computing will solve world hunger.

DARLING: It won't?

BILL: No it won't. 

DARLING: I was being sarcastic. 

BILL: Anyway, the coverage pushed two points

a) IMPRESSIVE that a computer could FIND these things that humans could not. This is TRUE (gee, how do I know that? The Gell-Mann Effect,  is that people disgusted when they read a newspaper article on something they know about and find the mistakes later assume that the other articles are fine. SHOUT OUT to Jim Hefferon who telling me the name Gell-Mann Effect and left a comment with a pointer. The original version of this post had a BLANK there.) 

b) The algorithm is practical! They did not quite say that but it was implied. And certainly there was NO mention of it only working in GF(2). And I was fooled into thinking that it might be competitive with Strassen. 

READERS (of this blog entry, I predict) Uh, Bill, the popular press getting science news wrong and saying its more practical than it is probably predates the Bible. I can imagine  the Cairo Times in 2000BC writing `Scientists discover that in any right triangle with sides a,b,c  a^2+b^2=c^2 and this will enable us to build food silos and cure Hunger. In reality they knew that the 3,4,5 triangle was a right triangle, were no where near a proof of a general theorem, and I doubt it would have helped cure hunger. 

BILL: This time the news was REALLY CLOSE to what I do (if  R(5) is found by a computer and the media claims its practical I'll either have a very angry blog or repost my April Fools' day article on Ramsey Theory's application to  History) AND I posted incorrectly about it. So, to quote many a bad movie

THIS TIME ITS PERSONAL!