Blurry JPEG or Frozen Concentrate

Ted Chiang in a recent New Yorker article likened ChatGPT to a blurry JPEG, i.e. a "lossy compression" of the web. It's a good article but the analogy isn't quite right, there's a different kind of compression happening. Think of all human written knowledge as a random example of what could have been generated and we remove the randomness, like water is removed to make concentrated orange juice. We then add water (or randomness) to get back some version of the original. 

Lossless compression, like gzip, gives a compressed version of some data with the ability to reconstruct it exactly. It corresponds nicely to Kolmogorov complexity where K(x) is the smallest program p that generates the string x. p is a lossless compression of x.

Lossy compression, like JPEG, often allows much higher compression but with some error. In Kolmogorov terms you are trading off the size of the program p and some error function between x and the output of p. Most compression programs for pictures, music and video use algorithms designed for the specific medium. You can also use machine learning to get lossy compression by training both the compression and decompression algorithms.

Lossy compression tries to recreate the original picture. Generative AI, like ChatGPT, takes a different approach. Let's consider Wikipedia as this is the example used by Chiang. For any specific topic, there are many different ways to write a Wikipedia article, as good as or better than the article that currently exists. ChatGPT doesn't need to recreate anything close to the original article, just one that explains topic well. What we want is a description of a program p that corresponds to a set of possible Wikipedia articles, of which the real article is a random example of this set. An ideal version of ChatGPT would choose a random article from this set. Dall-E, generative AI for art, works a similar way, creating art that is a random example of what art might have been. 

In terms of Kolmogorov complexity, this corresponds to the Kolmogorov Structure Function, basically the smallest program p such that p describes a set S of size m that contains x. with |p| + log m ≈ K(x). The string x is just a random element of S, you can get a string like it by picking an element of S at random.

There is no recursive algorithm that will find p and we also need to limit ourselves to p that are computationally efficient, which means that generative AI algorithms may never be ideal and will sometimes make mistakes. That doesn't mean we shouldn't use them just that we need to be wary of their limitations. As the saying goes "All models are wrong, but some are useful".

When is a paper `Easily Available' ?

I was looking at the paper 

                                PSPACE-Completeness of reversible deterministic systems

by Erik Demaine, Robert Hearn,  Dylan Hendrickson, and Jayson Lynch (see here) and came across the following fascinating result which I paraphrase:

The problem of, given balls on a pool table (though it can be one you devise which is not the standard one) and each balls initial position and velocity, and a particular ball and place, it is PSPACE complete to determine if that ball ever gets to that place. 

Demaine et al. stated that this was proven by Edward Fredkin and Tommaso Toffoli in 1982 (see here for a link to the 1982 paper, not behind a paywall). Demaine et al. gave an easier proof with some nice properties. (Just in case the link goes away I downloaded the paper to my files and you can find it here.) 

I needed the bib reference for the FT-1982 paper and rather than copy it from Demaine et al. I wanted to cut-and-paste, so I looked for it in DBLP. I didn't find the 1982 paper but I did find a book from 2002 that reprinted it. The book, Collision-based computing, has a website here. The book itself is behind a paywall.

On the website is the following curious statement:

[This book] Gives a state-of-the-art overview of an emerging topic, on which there is little published literature at the moment. [The book] Includes 2 classic paper, both of which are widely referred to but are NOT EASILY AVAILABLE (E. Fredkin and T. Toffoli: Conservative Logic, and N . Margolous Physics-Like Models of Computation). 

The caps are mine.

Not easily available? I found a link in less than a minute, and I used it above when I pointed to the paper. 

But the book IS behind a paywall. 

Perhaps Springer does not know that the article is easily available. That would be odd since the place I found the article is also a Springer website. 

The notion of EASILY AVAILABLE is very odd. While not quite related, it reminds me of when MIT Press had to pay a few thousand dollars for permission (that might not be the legal term) to reprint Turing's 1936 paper where he defined Turing Machines (he didn't call them that), which is on line here (and other places), for Harry Lewis's book Ideas that created the future. 

Why Can't Little Chatty Do Math?

Despite OpenAI's claim that ChatGPT has improved mathematical capabilities, we don't get far multiplying large numbers.

Typical for ChatGPT, the answer passes the smell test. It has the right number of digits and has correct first and last couple of digits. But the real answer is 646382140418841070,  quite different from the number given.

As far as I know, multiplication isn't known to be in TC⁰, the complexity class that roughly corresponds to neural nets. [Note Added: Multiplication is in TC⁰. See comments.] Also functions learned by deep learning can often be inverted by deep learning. So if AI can learn how to multiply, it might also learn how to factor. 

But what about addition? Addition is known to be in TC⁰ and ChatGPT performs better.

The correct answer is 1612502411, only one digit off but still wrong. The TC⁰ algorithm needs to do some tricks for carry lookahead that is probably hard to learn. Addition is easier if you work from right to left, but ChatGPT has trouble reversing numbers. There's a limit to its self-attention.

ChatGPT can't multiply but it does know how to write a program to multiply.

It still claims the result will be the same as before. Running the program gives the correct answer 646382140418841070. 

ChatGPT is run on a general purpose computer, so one could hope a later version that could determine when its given a math question, write a program and run it. That's probably too dangerous--we would want to avoid a code injection vulnerability. But still it could use an API to WolframAlpha or some other math engine. Or a chess engine to play chess. Etc. 

After you are notified that an article is accepted...

 After just one round of referees reports

(they send me the reports, I made the corrections, they were happy) I got email saying my paper on proving the primes are infinite FROM Schur's theorem in Ramsey was ACCEPTED. Yeah! Now What? 

1) The journal send me an email with a link GOOD FOR ONLY FIFTY DAYS to help me publicize the article. Here is the link:

https://authors.elsevier.com/a/1gTyD,H-cWw6X

Will this really help? The article is already on arxiv. (ADDED LATER: the link on arxiv is here.)  Also, I can blog about it, but how do non-bloggers publicize their work? Do they need to? 

(ADDED LATER: A commenter wanted to know why I am publishing in an Elsevier journal. This was a memorial issue in honor of Landon Rabern (see here) a combinatorist who died young.  I was invited to submit an article.) 

QUESTION: Is this common practice? If so, what do you do with those links? Email them to all of your the people who should care about the article?

2) I got some forms to fill out that asked how many offprints I wanted. While my readers can probably guess what that means, I will remind you: paper copies of the article. I filled out the form:

I want 0 of them.

They still wanted to know the address to send the 0 copies to, so I gave that as well.

Does anyone actually get offprints anymore? That seems so 1990's. With everything on the web I tend to email people who want article pointers. In fact, that happens rarely - either nobody wants to read my articles (quite possible) or they find them on my website (quite possible). 

In 1991 when I went up for tenure the dept wanted 15 copies of every article I wrote so they could send my letter writers (and others) all my stuff. Rumor is that the Governor of Maryland got a copy of every article I ever wrote. I hoped he was a fan of oracle constructions. 

In 1998 when I went up for full prof they did not do this, assuming that the letter writers could find what the needed on the web. I do wonder about that- it might have been a nice courtesy to send them stuff directly and that would be a use for offprints. Depends on if my letter writers prefer reading online or on paper. They could of course print out my papers, but again- as a courtesy perhaps we should have supplied the papers. 

QUESTION: Do you order a non-zero number of offprints and if so why? 

3) The journal offered to have my article to be open access at their site for a price. I did not do this as, again, the article is already on arxiv.

QUESTION: Is there a reason to have your article formally open-access given that its already on arixv? 

4) One of my co-authors on a different article asked me When will it appear IN PRINT?  I can't imagine caring about that. Its already on arxiv and I doubt having it in a journal behind paywalls will increase its visibility AT ALL. The only reason to care about when it appears IN PRINT is so I can update my resume from TO APPEAR to the actual volume and number and year. 

QUESTION: Aside from updating your resume do you care when an article that was accepted appears IN PRINT? And if so why? 

Responsibility

Nature laid out their ground rules for large language models like ChatGPT including

No LLM tool will be accepted as a credited author on a research paper. That is because any attribution of authorship carries with it accountability for the work, and AI tools cannot take such responsibility.

Let's focus on the last word "responsibility". What does that mean for an author? It means we can hold an author, or set of authors, responsible for any issues in the paper such as

• The proofs, calculations, code, formulas, measurements, statistics, and other details of the research.
• Any interpretation or conclusions made in the article
• Properly citing related work, especially work that calls into question the novelty of this research
• The article does not contain text identical or very similar to previous work.
• Anything else described in the article.

The authors should take reasonable measures to ensure that a paper is free from any issues above. Nobody is perfect and if you make a mistake in a paper, you should, as with all mistakes, take responsibility and acknowledge the problems, do everything you can to rectify the issues, such as publishing a corrigendum if needed, and work to ensure you won't make similar mistakes in the future.

Mistakes can arise outside of an author's actions. Perhaps a computer chip makes faulty calculations, you relied on a faulty theorem in another paper, your main result appeared in a paper fifteen years ago in an obscure journal, a LaTeX package for the journal created some mistakes in the formulas or a student who helped with the research or exposition took a lazy way out, or you put too much trust in AI generative text. Nevertheless the responsibility remains with the authors. 

Could an AI ever take responsibility for an academic paper? Would a toaster ever take responsibility for burning my breakfast?

 

Why does pi come up so often? I don't know either but ...

 Here is how history DID unfold:

1) People noticed that the ratio of the circumference to the diameter of ANY circle is always the same, it's a number between 3 and 4, roughly 3.14 or as my Dad would say, exactly 22/7 (see this blog post). On the web (see here) is a claim that Euler first used the symbol pi since it is the first letter of a Greek word for Circumference. I've seen other sites that claim someone less famous and its the first letter of a Greek work for Perimeter. 

But in any case pi was known (though not called that) a LONG time ago.

2) MUCH LATER people noticed

1/1^2 + 1/2^2 + 1/3^2 + ... = pi^2/6 (Euler showed this in 1735, see here. That site says that it was Basel's problem to determine the sum. Yeah for Basel--- his name lives on even after his problem was solved! This did not happen for Baudet and Vazsonyi. If you don't know what they conjectured--- well, that proves my point. ADDED LATER: commenter Robert pointed out that Basel is NOT a person's name but a cities name. I am delighted to know that!) 

1 - 1/3 + 1/5 - 1/7 + 1/9 ... = pi/4 (Leibniz showed this in 1676, see here. A good Quora site on that sum is here.)

(There are other series where pi comes up as well.) 

3) People wonder Why did pi, which has to do with CIRCLES, end up in INFINITE SERIES?

What if history unfolded the other way: 

1) People noticed

1/1^2 + 1/2^2 + 1/3^2 + ... =a^2/6 (Euler did that in 1735, see here.) 

1 - 1/3 + 1/5 - 1/7 + 1/9 ... = b/4 (Leibniz showed this, see here. A good Quora site on that sum is here.)

and they noticce that a=b and is between 3 and 4, closer to 3. They decide to call it pi for no good reason. 

(There are other series where pi comes up as well.) 

2) MUCH LATER people noticed that this same funny constant pi was the ratio of circumference to diameter in any circle. 

3) People wonder Why did pi, which has to do with INFINITE SERIES, end up in CIRCLES?

The following comic captures the dichotomy: here

Back to the 90's

The current state of computer science reminds me of the early excitement of the Internet in the mid-90's. By the beginning of the 90's, computers landed in many homes and most offices. Computers had modems, connected through the phone lines. Various online service networks, CompuServe, Prodigy, AOL, MSN, started up which provided some basic information and communication but were mostly walled gardens. 

But then came the mosaic web browser in 1993. There weren't many web pages and they looked awful. There is a special place in hell for whomever invented the <blink> tag. But the ability to link to other pages, local or anywhere else on the web, was a game changer. I quickly created a web page so people could download my papers, to try it out and because I got tired of responding to email requests for them. People experimented with all different kinds of things on the web. Companies tried to figure out what to put on web pages. The online service networks reluctantly put browsers on their sites.

In the mid-90's the Internet was exciting but messy. Search engines would brag about the number of pages they searched but the ranking lacked relevance. Every CS job talk in every subarea, including theory, focused on the Internet. VC money flowed into Internet-related companies no matter how silly. It wasn't until Google using the PageRank algorithm gave us a good search engine, the dot-com bust drove out the bad companies and cloud computing gave us good platforms that we got to the Internet we have today, for better or for worse.

We're at that messy stage with machine learning. We can see the game-changing potential of the technology but far too many problems limit our ability to use them. VC money flows into new ML startups while our traditional Internet companies are shedding jobs. Will the transformers paper be this generation's PageRank or do we need another trick to take the next step? If the Internet is any guide, we'll get past this early stage, the market will shake out, only to develop even more challenges down the line.

The Betty White Award for 2022

In Dec 2021 I noted in this post, which was my 1000th post ever (according to Ken Regan, see here) that Betty White had the misfortune of dying on Dec 31, 2021, so AFTER the People we said goodbye to in 2021 articles had already appeared. 

That might not be quite right since when she died it was Jan 1 SOMEWHERE in the world. I learned a new phrase- AWE- AnyWhere on Earth.  But no, she was not mentioned in the People we said goodbye to in 2022 articles.

The Betty White award goes to a celebrity that had the same fate- dying too late in the year to be mentioned in those articles. I had not thought of what criteria I would use if there is more than one option, and indeed, this year there are three candidates that I know of. 

Pele was the greatest soccer player of all time.  Died Dec 29, 2022, at the age of 82. 

Barbara Walters was a famous broadcast journalist. Died Dec 30, 2022, at the age of 93.

Pope Emeritus Benedict  was a prior Pope (obviously). Died Dec 31, 2022 at the age of 95. He died at 9:34AM Vatican Time. I do not think he died on Jan 1, 2023 AWE though that would not disqualify him since he surely will not be in the 2023 People we say goodbye to in 2022 articles.

So which one should get the award?

The term famous means famous when they died. They were all much more famous some years ago than they are now. I am using famous when they died as a criteria. 

a) I am not sure who is more famous internationally- Pele or Pope Emeritus Benedict. Walters is not famous internationally. 

b) Walters is more famous in America. I think Benedict is second, though its hard to tell.  Frankly none of the three are that famous in America. Walters was at one time. Fame is fleeting!

c) Benedict died older and later in the year.

d) Of the three, one was prominent in one of worlds largest religions. The others were a broadcast journalist and a former Pope. 

Rather than try to find a well defined criteria, I will give it the Betty White award to all three of them.

ADDED LATER: Lance has tweeted a poll so you can vote on who you think should have won the ward. The poll has you vote for one of the three, so you can't vote for two of the three, or (as I would have done) vote for all three. 

Note that  Martin Davis avoided being considered for the award since he died on Jan 1, 2023. 

Meta-Complexity

I'm sure many of you long-time readers are asking, "Why all this big focus on machine learning in your posts and tweets? You are the 'Computational Complexity' blog! You've barely said a word about meta-complexity."

So what is meta-complexity? From what I can tell the term goes back a few years but really came into wide use in computational complexity in the past year. The Computational Complexity Conference held an invited talk on meta-complexity by Rahul Santhanam, and the Simons Institute is hosting a research program this spring on the topic.

As the name suggests, meta-complexity studies the complexity of computing the complexity of various problems. It's a term that encompasses recent research into the Minimum Circuit Value Problem (given the truth-table of a Boolean function, find the size of the smallest circuit that computes it) and the complexity of time-bounded Kolmogorov complexity. 

To quote from the Simons page

Meta-complexity provides a unifying framework for a variety of important tasks in several important areas of computer science, including computational complexity, proof complexity, cryptography, and learning theory. These areas are all intimately linked, but only recently are these links being made explicit and studied more closely. For example, learning can be interpreted as solving search versions of the Minimum Circuit Size Problem and related problems. Basing primitives such as one-way functions and indistinguishability obfuscation on standard complexity assumptions is one of the main objectives in theoretical cryptography. Important recent directions involving meta-complexity within proof complexity, such as lifting and automatability, strengthen analogies and connections between proof complexity and circuit complexity. In addition, independence results such as the natural proofs framework have intuitive interpretations in terms of meta-complexity. These connections have led to several recent breakthroughs, including quasi-polynomial time PAC-learning algorithms for constant-depth circuits with parity gates, new worst-case to average-case reductions for NP problems, a new complexity-theoretic characterization of one-way functions, and the NP-hardness of automating resolution.

Not to mention the theorem of the year, Shuichi Hirahara's proof that determining the minimum circuit of a partially specified function is NP-complete. 

When you get down to it meta-complexity is all about learning, determining the complexity of finding programs. You cannot escape it.

To dive deeper into meta-complexity check out the videos of the Simons meta-complexity bootcamp. 

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.