University Challenges

Seems like US universities have been in the news quite a bit recently. You'd think for the great academics and research. Alas, no.

I decided to make a list of the not so unrelated topics. The list got long and still from from complete.

• Public perception of universities has been dropping. 
• Enrollment: Up in 2023 for the first time since the pandemic. But still down 900,000 undergrads since five years ago and the demographic cliff is just a couple years away.
• Fiscal Challenges even at Penn State and University of Chicago.
• On the other hand are those with huge endowments.
• Where have the men gone? While CS is still predominantly male, men make up only about 40% of undergrads on four-year colleges. The percentages are lower for African-American and Hispanic men.
• The increase in teaching faculty over tenure-track. 
• AI - How best to use it to help the educational process without letting students cheat, and where do you draw the line. 
• State government exerting control. We are seeing a number of conservative states pushing back against DEI and the perceived liberal bias.
• Affirmative Action - How do universities maintain a diverse student body in the wake the supreme court ruling last summer.
• Admissions policies that favor the rich, notably legacy admissions and sports other than football and basketball, where wealthier kids have the time, training and equipment to succeed.
• SAT - Most schools have eliminated the SAT exam but should they bring it back? 
• College is seen more as a place to build career skills. STEM fields especially in computing have seen huge gains in enrollment while humanities and social sciences have been decimated. How should colleges respond?
• Competition from certificate programs, online degrees, apprenticeships and boot camps.
• Athletics - Chasing ever-increasing broadcast revenue has restructured conferences (Goodbye Pac-12). Name-Image-Likeness has made some college athletes, notably in football and basketball, significant money. Alumni collectives and easier transfer rules have turned college student athletes into free agents. Meanwhile some lower revenue sports are getting cut.
• Colleges as a political football as college graduates trend democratic.

The Israel-Gaza-Hamas conflict alone has supercharged a number of issues.

• When and how should universities take a stand on political issues. 
• Congressional hearings into university policies
• Free speech, especially when it creates disruption, makes people feel unsafe and leads to discrimination. Where do you draw the line?
• Activist donors and boards. As universities rely more on "net-high worth individuals", these large donors can hold considerable sway, including pushing out presidents. 

So as a college professor or graduate student, how do you deal with all of the above? Best to ignore it all and focus on your research and teaching.

Certifying a Number is in a set A using Polynomials

 (This post was done with the help of Max Burkes and Larry Washington.)

During this post \(N= \{0,1,2,\ldots \}\) and  \(N^+=\{1,2,3,\ldots \}\).

Recall: Hilbert's 10th problem was to (in todays terms) find an algorithm that would, on input a polynomial \(p(x_1,\ldots,x_n)\in Z[x]\), determine if there are integers \(a_1,\ldots,a_n\) such that \(p(a_1,\ldots,a_n)=0\).

From the combined work of Martin Davis, Yuri Matiyasevich, Hillary Putnam, and Julia Robinson it was shown that there is no such algorithm.  I have a survey on the work done since then, see here
The following is a corollary of their work:


Main Theorem:
Let \(A\subseteq N^+\) be an r.e. set. There is a polynomial \(p(y_0,y_1,\ldots,y_n)\in Z[y_0,y_1,\ldots,y_n]\) such that

\((x\in A) \hbox{ iff } (\exists a_1,\ldots,a_n\in {\sf N})[(p(x,a_1,\ldots,a_n)=0) \wedge (x> 0)] \}.\)

Random Thoughts:

1) Actual examples of polynomials \(p\) are of the form

\(p_1(y_0,y_1,\ldots,y_n)^2 + p_2(y_0,y_1,\ldots,y_n)^2 + \cdots + p_m(y_0,y_1,\ldots,y_n)^2\)

as a way of saying that we want \(a_1,\ldots,a_n\) such that the following are all true simultaneously:

\(p_1(x,a_1,\ldots,a_n)=0\), \(p_2(x,a_1,\ldots,a_n)=0\), \(\ldots\), \(p_m(x,a_1,\ldots,a_n)=0\),

2) The condition \(x>0\) can be phrased

\((\exists z_1,z_2,z_3,z_4)[x-1-z_1^2-z_2^2-z_3^2-z_4^2=0].\)

This phrasing uses that every natural number is the sum of 4 squares.


The Main theorem gives a ways to certify that \(x\in A\): Find \(a_1,\ldots,a_n\in Z\)
such that \(p(x,a_1,\ldots,a_n)=0\).

Can we really find such \(a_1,\ldots,a_n\)?

A High School student, Max Burkes, working with my math colleague Larry Washington, worked on the problem of finding \(a_1,\ldots,a_n\).

Not much is known on this type of problem. We will see why soon. Here is a list of what is known.

1) Jones, Sato, Wada, Wiens (see here) obtained a 26-variable polynomial \(q(x_1,\ldots,x_{26})\in Z[x_1,\ldots,x_{26}]\) such that

\(x\in \hbox{PRIMES iff } (\exists a_1,\ldots a_{26}\in N)[(q(a_1,\ldots,a_{26}=x) \wedge (x>0)].\)

To obtain a polynomial that fits the main theorem take

\((x,x_1,\ldots,x_{26},z_1,z_2,z_3,z_4)=(x-q(x_1,\ldots,x_{26}))^2+(x-z_1^2+z_2^2+z_3^2+z_4^2)^2.\)

Jones et al. wrote the polynomial \(q\) using as variables \(a,\ldots,z\) which is cute since thats all of the letters in the English Alphabet. See their paper pointed to above, or see Max's paper here.

2) Nachiketa Gupta, in his Masters Thesis, (see here) tried to obtain the the 26 numbers\ (a_1,\ldots,a_{26}\) such that \(q(a_1,\ldots,a_{26})=2\) where \(q\) is the polynomial that Jones et al. came up with.  Nachiketa Gupta found  22 of them.  The other 4 are, like the odds of getting a Royal Fizzbin, astronomical.  Could todays computers (21 years later) or AI or Quantum or Quantum AI obtain those four numbers?  No, the numbers are just to big.

3) There is a 19-variable polynomial \(p\) from the Main Theorem for the set

\(\{ (x,y,k) \colon x^k=y\}.\)

See Max's paper here Page 2 and 3, equations 1 to 13. The polynomial \(p\) is the sum of squares of those equations. So for example \(r(x,y,z)=1\) becomes \((r(x,y,z)-1)^2\).

Max Burkes found the needed numbers to prove \(1^1=1\) and \(2^2=4.\) The numbers for the \(2^2=4\) are quite large, though they can be written down (as he did).

 
Some Random Thoughts:

1) It is good to know some of these values, but we really can't go much further.

2) Open Question: Can we obtain polynomials for primes and other r.e. sets so that the numbers used are not that large. Tangible goals:

(a) Get a complete verification-via-polynomials that 2 is prime.

(b) The numbers to verify that \(2^3=8\).

3) In a 1974 book about progress on Hilbert's problems (I reviewed it in this book rev col, see here) there is a chapter on Hilbert's 10 problem by Davis-Matiyasevich-Robinson that notes the following. Using the polynomial for primes, there is a constant \(c\) such that, for all primes \(p\) there is a computation that shows \(p\) is prime in \( \le c \) operations. The article did not mention that the operations are on enormous numbers.

OPEN: Is there some way to verify a prime with a constant number of operations using numbers that are not quite so enormous.

Learning Complexity on Your Own

The following request came from a comment earlier this month (shortened)

Could you give some advice on how to study complexity theory on one's own, and/or to follow the research frontier even to find one's own research topic, for someone with solid math and TCS background (say somewhere between Sipser and Arora & Barak), nonetheless an outsider? For example, what books/papers to read? How hard is it to follow all the important results? How would you determine whether a new paper is worth reading in full details?

Of course the short answer is to go to graduate school, and my question is mainly for those who don't have the luxury, partially motivated by ’t Hooft and Susskind on physics.

Let me suggest a backwards approach. Find interesting papers, by checking the latest proceedings in major conferences such as STOC, FOCS and Computational Complexity or those mentioned on blogs or Quanta. If you don't have access to the papers you can often find them on author's home pages or on arXiv or ECCC. First look at titles that interest you, then read the abstract, intro and the full paper. If you lose interest go on to another paper. 

Once you find a paper that excites you, start reading in details. When you find terms or references to old results you don't know, go do some research, either the cited papers or sites like the Complexity Zoo, Wikipedia and TCS Stack Exchange. You can also find videos and lecture notes on various topics. Large language models like ChatGPT can help understand concepts but have a healthy skepticism on what it says, particularly on specialized material.

As your read the cited papers, repeat the process. You basically doing a depth-first search through the literature. If you do this for a paper like Ryan Williams' NEXP is not in ACC\(^0\), you'll get a pretty well-rounded education in complexity. 

A paper that every Undergraduate should read

 The paper As we may think

by

Vannevar Bush 

appeared in

The Atlantic Monthly, in July 1945.

 I first read it since it was one of the papers in Ideas that Created the Future: Classic Papers in Computer Science which I reviewed  here.

The link to the paper is  here.

This paper predicts so much about the future that it should be  read by every undergraduate. Not every Undergraduate computer science major, but every undergraduate.  I am teaching Honors Discrete Math (Freshman and Sophomores) and Automata Theory (Juniors and Seniors) and on hw00 they are required to read the paper and write about two advances that were predicted.

I now ask my readers to do the same: Read it and

a) Leave comments about what was predicted that came true.

b) Leave comments about what was predicted that did not come true. 

c) Leave comments on anything related to the paper that you want to.

Enjoy!

Offer Timing

In most academic fields, departments, either formally or informally, have their interviews and make their junior faculty offers at about the same time. Faculty candidates know their options and decisions get made quickly. 

Not so in computer science, decentralized by design. Interview and offers are made from January through June (or beyond). Candidates sometimes will hold an offer for months to see if they will eventually get an offer that fits them better. Finding jobs in a the same location for partners further muddles the water. This is certainly a topic I've tackled before but I've lost hope that we'll ever see real reform in CS faculty recruiting. So how should departments time their offers.

I tried many different strategies when I was department chair at Georgia Tech. We tried making offers early, say in February, but by the time these candidates were ready to decide months later your university is out of their recent memory. Some department try to make early offers with short strict fuses. I don't like that approach--it puts undue stress on young candidates and creates resentment even if successful. Candidates will also use early offers as leverage to get offers out of other schools.

On the other hand if you hold off too long, you may lose the candidate to another university or not have time to find a position for the partner.

I found the sweet spot is early April to start making offers, though you need to hold off faculty chomping at the bit to make offers earlier. But that's the job as chair. As the saying goes, if a coach starts listening to the crowd, he soon becomes one of them.

I've heard the argument that not making an offer right after the interview makes the candidate feel they we didn't want them. That goes away if you say upfront you hold off offers until April and stick to it. 

If a candidate tells me that they have another offer with a "tight" deadline, I tell them to push back. Almost all departments will give an extension rather than losing a good candidate.

Every rule has their exceptions. If a candidate you want says they'll accept an offer if you make it now and you believe them, go ahead and lock them up. If there is a risk that holding on making an offer means that position might disappear for financial or other reasons, then make those offers earlier.

My secret plan is that every department steals this strategy, we all make offers at the same time, and the reason for this post goes away. 

A nice dice problem-Part 2

In my last post (see here) I posed a dice problem, promising to give the answer in the next blog which is this blog. Here is the problem from my last blog:

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

In this blog I pose a dice problem. The problem is NOT mine and the answer is KNOWN. However, I DO NOT  think its well known, and I DO think it's interesting. My next post will have the answer. 

PROBLEM:

A 6-sided fair die is a 6-tuple of positive natural numbers. (NOTE- POSITIVE NATURAL NUMBERS SO YOU CANNOT USE ZERO. I am emphasizing this since some answers in the comments used 0.) 

The standard 6-sided die is (1,2,3,4,5,6).

Do there exist two 6-sided dice  \(a_1,\ldots,a_6\) and \(b_1,\ldots,b_6\)  (the numbers need not be distinct) such that

a) The dice are NOT standard.

b) When you roll the two dice you get THE SAME probabilities of sums as rolling two standard dice (we are assuming the dice are fair so the prob of any side is 1/6, though if a die has two faces with 4 pips on them, then of course the prob will of getting a 4 will be 1/3). So, for example, the probability of getting a sum of 2 is 1/12, the probability of getting a sum of 7 is 1/6.

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

Some pips on this:

a) This problem was posed and solved in a Martin Gardner column, and later generalized by Gallian and Rusin (the paper is here). I did a write up of just the two 6-sided dice case and a few other things here. I also have slides on the problem here.

b) The only answer is (1,2,2,3,3,4) and (1,3,4,5,6,8).  Here is the first step of the solution, though better off reading my writeup pointed to in item a.

We seek \(a_1,\ldots,a_6\) and \(b_1,\ldots,b_6\)  (NOT (1,2,3,4,5,6)) such that

\((x^{a_1} + \cdots + x^{a_6})(x^{b_1}+ \cdots + x^{b_6}) = (x^1 + \cdots + x^6)^2 \).

Using polynomials also lets you solve the problem for other types of dice, as shown in my writeup, my slides, and the original paper. (Spellcheck thinks writeup is not a word. I disagree.)

c) How did I find this question, and its answer, at random? I intentionally went to the math library, turned my cell phone off, and browsed some back issues of the journal Discrete Mathematics. I would read the table of contents and decide what article sounded interesting, read enough to see if I really wanted to read that article. I then SAT DOWN AND READ THE ARTICLES, taking some notes on them. 

d) This is more evidence that perhaps we should unplug, at least partially, sometimes. I blogged about that here.

e) Technology is NOT the real issue here. Its allowing yourself the freedom to NOT work on a a paper for the next STOC/FOCS/WHATNOT conference and just read math for FUN without thinking in terms of writing a paper. I am supposed to say you never know when random knowledge may help you get a result but that's the wrong mentality since it circles back to being non-random as you will only read things that you think will lead to results.

f) The STEM library at UMCP stopped getting PAPER journals a while back. Hence the only journals I can look at are before a certain date. Should the STEM library subscribe to paper journals just so I can read journals at random? OF COURSE NOT. Instead I may in the future surf the web in an intelligent way looking for random article I find interesting. I have sometimes used arxivs for this, though I also sometimes go into a NON-PRODUCTIVE black hole.

g) Older journals are sometimes more readable. The STEM library still has plenty of them, so I might not need to use the web for this for a while. 

h) For the purposes of random browsing, journals that are focused and whose name says what their focus is (e.g., Discrete Math, Journal of Symbolic Logic, Conference on Topological Algebraic Topology) are good since you know what's in them and hence if you care (or have enough background knowledge). By contrast, a journal title like Proceedings of he London Math Society or Duke Mathematics Journal or Southern North Dakota Math Journal don't tell you anything about what's in them, so its not worth looking at for this purpose.

i) SO, is the dice problem I posted on well known. From the comments on the original post, and my own observations, here are arguments for YES and for NO.

YES, Well known: (i) There is a name for these kind of dice, Sicherman dice. (ii) There is a Wikipedia page on Sickerman dice here. (iii) You can buy Sicherman dice here. (iv) The problem is in the book Concrete Mathematics as an exercise in Chapter 8, page 431. (v) There a Martin Gardner column, so it was well known at one time (though that may have faded). 

NO, Not Well known: (i) I had not heard of it and I've been around math and dice (I have a paper on loaded dice) for a long time. (ii) Lance had not heard of it. (iii) Some of my readers had not heard of it.

UPSHOT: The notion of well known is not well defined; however, if some of my readers did not know it, and are now enlightened, then I am happy.

Guest Post by Mohammad Hajiaghayi on SODA Business Meeting 2024

This is a guest post Mohammad Hajiaghayi on the SODA business Meeting from 2024. The meeting was held in Alexandria Virginia, Jan 7-10, 2024. The following meetings were held jointly:

SODA: ACM-SIAM Symposium on Discrete Algorithms

ALENEX: SIAM Symposium on Algorithmic Engineering and Experiments

SOSA: Symposium on Simplicity in  Algorithms

The website for SODA 2024 is here.

And now the guest post:

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

SODA Business Meeting Report:

After a few years of being unable to attend the SODA business meeting due to factors like Covid, I was able to participate this time, especially since it took place nearby in Alexandria, VA. So I thought it's a good idea to provide a brief report on the business meeting.

DISCLAIMER: Please be aware that this report is solely based on MY PERSONAL recollection of the meeting and is intended solely as an informal update.

The session started with Piotr Indyk, the chair of the SODA Steering Committee, presenting a slide outlining the meeting agenda. Following that, SODA24 PC Chair David Woodruff gave a brief overview of SODA24's numbers, including the record-high number of submissions, exceeding 650. Following that, Seth Pettie, SOSA PC Chair, shared a concise overview, highlighting the enjoyable experience of being a PC in SOSA, where papers are typically short, often less than 15 pages, emphasizing simplicity in algorithms.Best paper awards were then presented for both SODA and SOSA, detailed  here  and Greg Bodwin's An Alternate Proof of Near-Optimal Light Spanners for SOSA. Pettie bragged about a distinctive trophy for SOSA's best paper authors, in contrast to SODA, which only offers paper acknowledgments for awards. :)

Looking ahead, SODA is scheduled for New Orleans next year, followed by Vancouver in the subsequent year.

The majority of the discussion focused on the acceptance rate for PC submissions, particularly as David mentioned since the process is double-blind, and the PC is sizable, allowing PC members to submit can enhance the overall paper quality. Initially  at around 42%, significantly higher than the average acceptance rate of 29%, the Steering Committee of SODA requested a reduction to 35% for PC submissions this year.

In the past year, the fixed rate was 30%, prompting a debate on determining the appropriate acceptance rate. Nikhil Bansal shared insights into the acceptance rate of FAMOUS AUTHORS (authors with more than 20 papers in SODA) over the past few years, revealing no significant changes. While some argued against controlling the PC acceptance rate, I think the summary was to examine the average acceptance rate of PC members who were not part of the PC in the past few years. This evaluation could potentially guide the establishment of a threshold rate. This aligns with a truthful mechanism that I discussed with David Woodruff before the session.

During the discussion of PC submissions, Mikkel Thorup raised a subtle point about double-blind submissions,  where the authors might subtly boast about their results compared to their own previous work, potentially resulting in incremental advancements, as improving upon others is highly regarded in our community. I believe PC members, rather than reviewers, should diligently verify such claims for all papers, particularly regarding previous work, without the need for author names.  Additionally, if necessary, the PC could inquire with the PC chair who has access to the authors' names for cross-referencing with previous works.

Last but not least, in the concluding business segment of the meeting, I expressed my satisfaction with the adoption of double-blind submissions as the default for SODA/STOC/FOCS, consistently advocating for it in theory conference business meetings and behind the scenes (e.g., refer to my earlier conversation with SODA founder, the late David Johnson, here.) Despite experiencing increased difficulty in getting my own papers accepted in a double-blind SODA, being ranked second among SODA Famous Authors by DBLP (as defined by Nikhil), I firmly believe that double-blind submissions are the correct and fair approach. This is based on the principle that an author's name should not influence the fate of a scientific claim. I also voiced my happiness at the extensive discussion on fair policies for PC authors and even advocated for transparent criteria in selecting PC Chairs for SODA/FOCS/STOC. I stressed in particular the significance of valuing contributions to the conference, commonly measured by the number of papers, in selecting PC Chairs as those who dedicate effort to a conference should have a say in the process. This stands in contrast to relying solely on potentially biased personal opinions when such a quantitative criterion does not exist. Regardless, I highlighted the need for transparency in any criteria used to select a PC Chair, who can contribute further to diversity by forming the PC. I suggested discussing these criteria in business meetings, akin to our approach to other topics, to foster fairness, a sense of belonging, and prevent the conference from becoming an Insider Club (the term used by Martin Farach-Colton during the meeting), ensuring inclusivity.

A nice dice problem- Part I

In this blog I pose a dice problem. The problem is NOT mine and the answer is KNOWN. However, I DO NOT  think its well known, and I DO think it's interesting. My next post will have the answer. 

PROBLEM:

A 6-sided fair die is a 6-tuple of positive natural numbers. (NOTE- POSITIVE NATURAL NUMBERS SO YOU CANNOT USE ZERO. I am emphasizing this since some answers given used 0.) 

The standard 6-sided die is (1,2,3,4,5,6).

Do there exist two 6-sided dice  \(a_1,\ldots,a_6\) and \(b_1,\ldots,b_6\)  (the numbers need not be distinct) such that

a) The dice  are NOT standard

b) When you roll the two dice you get THE SAME probabilities of sums as rolling two standard dice (we are assuming the dice are fair so the prob of any side is 1/6, though if a die has two faces with 4 pips on them, then of course the prob will of getting a 4 will be 1/3). So, for example, the probability of getting a sum of 2 is 1/12, the probability of getting a sum of 7 is 1/6.

A few pips for now:

a) Try to get a method to solve it for two d-sided dice. Or other generalization.

b) You may post the answer or whatever thoughts on the problem you want; however, if you want to solve it without any hints, don't look at the comments. 

c) I do not know how hard this problem is to solve since I read the solution before really trying to solve it. I do not know how hard it is to find the answer online since I found the paper at random. 

d) I think the problem is not well known. I could be wrong. Leave comments if you've heard of it or not heard of it or whatever, to comment on that point. Note that well known is not a well defined term.

 

Favorite Theorems 2015-2024

In 1994, the FST&TCS conference invited me to give a talk at their meeting in Madras (now Chennai). I was in my tenth year as a complexity theorists since I started graduate school and looked back at a very impressive decade in computational complexity. So for the talk and corresponding paper (PDF) I went through my favorite ten theorems from 1985-1994, and used them to describe progress in a slew of subareas of complexity. 

In 2002 I started this blog and in 2004 decided to repeat the exercise for the following decade, and again in 2014. I also went back through my favorite theorems from the early days of complexity, 1965-1974 and 1975-1984. 

It's 2024 and as I approach my fortieth year in complexity, it's time once again a time to look back through the sixth decade of the field, still producing amazing results in a now mature field. I'll announce one theorem a month from February through November with a wrap-up in December. The choices are mine though feel free to send me your nominees. I choose theorems not based on technical depth but on how they change the way we think about complexity with an eye towards hitting may different subareas of the field.

See you in February where we'll go back to 2015 for a theorem decades in the making.

The Betty White Award for 2023: Tommy Smothers

Betty White died on December 31, 2021. When I mention that, even now, some people are surprised that they didn't hear about it. Why? Because she died AFTER all of the who we said goodbye to this year articles have come out. I think its idiotic to have these things come out in DECEMBER instead of early January.  Same with Time Magazine's Person of the Year. If Joe Biden had managed to create peace between Israel and the Palestinians AND between Russia and Ukraine on Dec 31, then he might, just might, have been a better choice than Taylor Swift for Person of the Year.

BUT, rather than complain, I created The Betty White Award for famous people who die towards the end of December. 

Past Winners:

2006: James Brown and Gerald Ford. I didn't have the award then but I noticed their deaths coming to late in the year to be noticed, see my post  here.

2021: Betty White and Bishop Tutu. See my post here. I didn't quite have the award then, but its implied.

2022: Pele, Barbara Walters, Pope Emeritus Benedict. See my post here.

I thought based on these three data points that I would often have 2 or more winners. But no. For 2023 there is one winner:

Tommy Smothers who died on  Dec 26, 2023 at the age of 86.

Tommy and Dickie Smothers (his brother is still alive at the age of 85)  were known as The Smothers Brothers. They did Comedy and Music together. They are more known for their comedy. A few notes

0) I wrote this post on Dec 31. I was going to post it on Dec 31 at 11:00PM but then thought What if someone famous dies in the next hour? Then I'll need to redo the post, probably giving both that person and Tommy Smothers the award!  I waited until Jan 2 since its possible that someone famous dies and I don't hear about for a few days.

1) They had a comedy-variety show The Smothers Brothers Comedy Hour from Feb 1967 to June 1968. It was controversial at the time for some of its political comments though, frankly, if you saw it now I really don't see why they were controversial.  They had very high ratings but were cancelled because of the controversy. I don't understand that either- if its making the network money, then why cancel it? Possibilities:

a) They were losing sponsors. I have not read that this was the case. And I would think they could get new ones.

b) Some local stations refused to air it. This seems to be true.

c) The suits themselves were offended and put their principles above profits. 

d) They were scared that the FCC would crack down on them.

e) They got angry letters (this is true though I don't see why this means you cancel).

What controversy? They made fun of the president! They were against the war in Vietnam!

So I am puzzled that they were cancelled. 

I was young at the time  and didn't really understand it (I still don't) but I recalled a great Mad Magazine piece about it (in 1968).  And thanks to the wonder of the internet, I found it in about 5 seconds. Here it is: here.  I suspect that my young readers are not at all surprised that an article I read over 50  years ago I can find easily. This still surprises me. And I note that its not always so easy.

2) The show was one of the first to do political humor about real living politicians (Another one was That was the week that was which had Tim Lehrer on it, among others.) Comedy featuring a generic politician being, say, dishonest, was certainly allowed, but not an actual one with current issues. As such it lead the way for SNL, The Daily Show, and other shows. 

3) While Smothers Brothers sounds like a made up name, their last name really was Smothers. Reminds me of Clint Eastwood and Dolly Parton having great stage names for their real names.

4) One of their types of comedy was to start singing a real song (they were good singers- folk singers) and then in the middle of it get into an argument or discussion about it. Here is an example: here. (warning- this is NOT controversial or political)

5) There was one episode that never aired because of its controversy.  Here it is: here. I watched it. I cannot see what is controversial in it. There is also some commentary after it that explains why it was controversial.

More odd- I didn't find it that funny. And note that this is the kind of thing I usually DO find funny. But this is not a criticism- its just evidence that some shows (or art in general) has a short shelf live.

6) That one episode being on you tube reminds me of the ONE picture of FDR in a wheelchair is ALL OVER the web. Here is one place: here. Not just the web--- it was in my High School History Text with the caption a rare photo of FDR in a wheelchair. Even then I doubt it was rare since it was in many textbooks. And now being on the web makes it even harder to say its rare. I did a post a long time ago (I was a guest blogger) on how things on the web can't really be considered rare. Its here.

7) The fact that they were controversial then but would not be now reminds me of the TV show Tanner 88, which was on HBO in 1988 (one of their first original series) which followed the fictional presidential campaign of Jack Tanner. At the time it was considered biting political satire. I bought the DVD and watched it in 2008. A typical episode of West Wing (a good show, but hardly a biting political satire) had more bite. But again, much like The Smothers Brothers, it paved the way.Which brings up back to our original point:

 Tommy and Dickie Smothers: We THANK YOU for paving the way for political satire and commentary.  

 

 

2023 Complexity Year in Review

Result of the year goes to 

Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren and Rahul Santhanam

An impressive year for complexity and we wrote several theorem posts this year including the one above, new Ramsey bounds, exponential circuit bounds for \(\Sigma_2^E\), inverting compression functions and advances in group isomorphism. 

It's a year dominated by wars, Taylor Swift, ChatGPT and mathematicians Leaning in. The blog word of the year is meta-complexity.

We remember Jimmy Buffett, Martin Davis, Neil Jones, Abraham Lempel, Gordon Moore, Roger Schank, Vera Sós, William Wulf, Jacob Ziv and Dilbert. Happy to forget Ted Kaczynski. 

Thanks to our guest posters Eric Allender, Ravi Boppana, Josh Grochow, and Youming Qiao.

Enjoy the holidays and we'll see you in 2024.

Archimedes, Pi, and Pickelball

I typed 

3,1,4,1,5,9 

into OEIS and,  as expected, I found that these are the first few digits of \(\pi\). See here.

I then read on the page:

\(\pi\) is sometimes refereed to a Archimedes constant, because the Greek mathematician computed lower and upper bounds of \(\pi\) by drawing regular polygons inside and outside a circle. 

In my 40 or so years being involved with math, I have never heard \(\pi\) called Archimedes constant. Whats going on here?

(a) The term is STILL in use I just happened to never hear it. I noted in a blog here that I didn't have a single book on trig in my house, so this is plausible.

(b) The term is NOT in use but the person who wrote that entry either is rather old or THOUGHT it was in use or heard it once when he was 10 years old or...

(c) Some weighted sum of (a) and (b) 

I suspect the term is NOT in use anymore. So when was it in use, and when did it fall out of favor? 

More random thoughts

1) I googled why is it called pi but it was auto filled to ask why is it called pickleball. I'll report on both:

pi: It was first called pi  in 1706 by [The Welsh Mathematician] William Jones because pi is the first letter in the Greek word perimitros which means perimeter. (ADDED LATER- the comments say that the question-and-answer are not as simple as this quote would imply. I am sure they are right.) 

Pickleball: This website here says the following. Joel Pritchard invented the game (the story is more complicated than that). With that in mind here is a direct quote:

Okay, now you know how it all started but the question we’re all thinking still remains: why do they call pickleball, well, pickleball? According the to U.S.A. Pickleball Association, the origins of the name differs between different accounts.

Joel Pritchard’s wife, Joan, started to call their game pickleball because “the combination of different sports reminded me of the pickle boat in crew where oarsmen were chosen from the leftovers of other boats.” But according to Barney McCallum, they named the game after Pritchard’s dog, who was (as you might’ve guessed) named Pickles! Despite the sour taste of actual pickles, their dog was sweet and known to run off with the ball while it was still being played!

Depending on who you ask, both accounts of the game’s name may actually be true. At the start, there wasn’t any name for pickleball until an official one was needed when the game started to gain traction. With the laid-back nature of pickleball, it’s only appropriate that it was named in a similar fashion.

Respect

I've generally avoided talking about all the events at college campuses in the last few months that came to a head at the congressional hearings last week that led to the resignation of Penn's president Liz Magill. It's not that I don't have any thoughts to share, rather I have too many that I'm still trying to process. 

I had planned to put them in writing this week but I can't. Not yet.

So one word for this season to hopefully recapture what we've seem to have lost: Respect.

Where do Journals go to Die?

In 2011 I had a post, here, about a real journal called The Antarctica Journal of Mathematics. Note that I put in the link in the last sentence; however, if you go there you will get to a page that IS labelled with the name of that journal, but all of the links on it are either broken or go to a place to sell domain names. I assume the journal is dead, but I can't find any evidence that it was ever alive. When I googled it I got the link above for the first hit and my 2011 blog post for the fourth hit.

On Wikipedia I found a debate about deleting the Wikipedia webpage for it, which I assume won since there is no webpage for it.  Here is that webpage: here.  That page also debates whether the journal was a joke, though they conclude that it was not a joke.

 

If you try to go to The Journal of Combinatorics and Number Theory using that link you will find

a) There is a page, but it says that the  journal is discontinued.

b)  You can click to see the table of contents from Vol 11, No 1 to Vol 12 No. 3.

c)  There is a mechanism to click on stuff and BUY articles from those issues but I do not know if it works, and I am not going to find out.

d) For issues before Vol 11, there is a place to click for prior issues. When you click on it you get to the NOVA publishers webpage but no indication of where to go for prior issues of this particular journal.

e) There is no Wikipedia site for the journal. That might not mean much, there is no Wikipedia site for  Raegan Revord either, and she deserves one (I linked to her IMDB page). (UPDATE- Raegan Revord now has a Wikipedia page here.)

f) Why do I care? Actually, I don't care much. However, I DO have an article in that journal, co-authored with Larry Washington and Sam Zbarsky. It was refereed seriously and we were never asked for money, so (1) its probably not a scam, and (2)  there was some quality control  (or the referee didn't get the memo). It was in Volume 10, No. 1. There is  no way for me to verify that it was ever published. Fortunately I will never have to. Also, the paper does not need to be published to be known since (1) I blogged about it  here and (2)  its on arxiv's here. Someone read it (probably on arxiv) and wrote a followup paper, see here.

 

QUESTIONS

1) Why did The Antarctica Journal of Mathematics die?

2) Why did the Journal of Combinatorics and Number Theory die?

If an author publishes in a journal that dies, and the journal does not maintain a good website, how can the author prove that he published there, if they need to? For a paper journal they may have a paper version of the journal, but for an e-journal they may be SOL.

If the paper is not on arxiv (or a similar site) it may be lost forever. Note that even if you wanted to pay for an article in either of those journals, it might be impossible. 

3) I wonder- are journals losing money since people are using arxiv and hence not buying the journals?

I only use journals to get credit from my school for publishing, and to get a good proofread from the referee. NOT to get an article out there. Thats what arxiv is for! Also, in my case I can email my article to the few people who care. And I can blog about it. 

Do We Need to Formalize?

Back in the 1990s I explored the system Nuprl for formalizing mathematical proofs. We had a theoretical paper on quickly checking a proof and I wanted to see if we could code it up and make it work on some simple theorems. It never went anywhere.

Automated proof systems have come a long way. Yesterday Terry Tao announced that he has fully formalized his proof with Tim Gowers, Ben Green and Freddie Manners of the Polynomial Freiman-Ruzsa (PFR) conjecture over \({\mathbb F}_2\) in the Lean proof system. The process from paper to formalization took about three weeks.

It's an impressive feat--major new theorem to full formalization in weeks. There's a nice Quanta article from 2021 about the Lean system formalizing a different result.

Is this just a novelty or do we gain something from the formalization?

Mathematics has done quite well without full formalization of theorems--we trust papers that give enough details of a proof that we know a full formalization is possible but fully formalizing a proof just didn't seem an efficient use of a mathematician's time. Should we not trust the proof of the Green-Tao theorem that there are arbitrarily long arithmetic progressions in the primes if we don't have a full formalization?

It would be interesting if formalizing in Lean led to new theorems or found serious bugs in "proofs" of old theorems. 

Maybe AI combined with strong proof systems in the future will be able to take a well-written math paper and find a fully formalized proof or output a logical gap. That would be great--a reviewer can focus on the value of a result instead of its correctness. But we are a long way from unassisted formalization.

Concepts like Turing Machines are hard to fully formulate but somebody did it and there's a lengthy discussion of formalizing computational complexity. So perhaps we can require that anyone who claims a solution to P vs NP needs to formalize their proof before they get to post it to arXiv. For me, that would be the killer app for Lean.

Where do Non-Primitive Recursive Functions come up NATURALLY?

The following is a conversation between Clyde Kruskal and Bill Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any non-primitive recursive functions that people actually want to compute. (See here for a definition of Primitive Recursive. Also see here for Ackermann's function which is computable but not primitive recursive.) 

BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is  exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable and  grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that. 

5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of  cells, with the cells being either occupied or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up.  (b) Is the constant reasonable?

8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry.  A much better song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my class.

(ADDED LATER: Quanta had a nice article on non-primrec functions recently here. The problem they are talking about is discussed in the comments.) 

The Engineer and The Computer Scientist

What is the difference between engineering and computer science? CS is not an engineering field, though there is some overlap. It's not the digital versus physical. To capture the difference we can look two tech CEOs dominating the news recently, Elon Musk and Sam Altman.

Engineers are problem solvers creating or improving technologies to reach a goal. Tesla has led the way for cars to become electric, connected and autonomous. SpaceX has develops highly capable rocket technology at lower cost. Ultimately though Tesla makes cars that go from A to B and SpaceX sends stuff into space. When Musk bought Twitter he focused on the engineering, but Twitter's challenges were not in its engineering and this is why Twitter/X has been floundering.

Computer scientists make platforms. The Internet, cloud computing, programming languages, mobile computing, cryptography, databases, social networks even NP-completeness don't focus on individual problems, rather they create environments that users and developers can apply to a variety of new applications and challenges.

AI is no exception. OpenAI has no specific goal or purpose it is trying to solve. There's AGI but that's more of a vague benchmark that may (or may not) be passed as ChatGPT and its successors continue to improve.

AWS, Python, Apple and OpenAI all have developers conferences. Tesla and SpaceX do not. Elon Musk has actually made Twitter/X harder for developers to build on. I don't hold high hopes for Grok.

It's not a perfect division, many engineers create platforms and computer scientists tackle specific problems. Nevertheless it's a good way to see the distinction between the fields.

Don't think the CS way is always the better way. You have less control of platforms, they can act in unexpected ways and people can use them unintentionally or intentionally to cause harm. Mitigating those harms is a challenge we must continuously address.

Can I make money in the betting markets based on what i ``know'' about the Republican VP choice

The betting markets for the Republican VP are here.

Assume that I am very confident that the VP won't be Nikki Haley. I can buy a NO share for 90 cents (that may change by the time you read this). If I buy 1 shares of NO for Haley for 90 cents then

IF she is NOT the nominee I get 100 cents, so a profit of 100-90= 10 cents. 

IF she IS the nominee I lose the 90 cents.

More generally, if I buy x shares then 

IF she is NOT the nominee I get 100x cents so, so a profit of 100x-90x=10x cents.

IF she IS the nominee then I lose the 90x cents. 

SO, if I am so confident, why not buy x shares of NO on Haley where x is large?

That depends on how confident I am. 

I am VERY CONFIDENT that if Trump is the Nominee then Haley is NOT the VP. Say I think the probability of this is \( p_1\) (very close to 1. \(p_1\) could be 0.999).

I am CONFIDENT that Trump will be the nominee.  Note that I didn't say ``VERY''. I think the probability of this is \(p_2\) (not as confident- say 0.95). 

So my expected value is (ignoring some other cases)

\(10xp_1p_2 - 90(1-p_1p_2)x = x(10p_1p_2 - 90(1-p_1p_2))\).

So to make a profit I  need \(p_1p_2 > \frac{9}{10} \). 

With my estimates \(p_1=0.999\) and \(p_2=0.95\) I should make the bet. But I won't.

1) I can imagine a world where Trump does not get the nomination- health or legal problem. Legal might not stop him--- recall that Eugene Debs ran for president while in jail, as the socialist candidate (a third party) and got 3.4% of the vote. When I google list all of the people who ran for president from jail Eugene Debs is the only person I found. I suspect there are others but they were fourth party candidates. Trump  might be ineligible to run based on some interpretation of the 14th amendment, though I doubt that will happen.

2) I cannot imagine a world where Trump gets the nomination and picks Haley as his VP. So if I could make an IF-THEN bet that it WON"T be the case that Trump is the nominee and Haley is VP, I might do that. But again, weird things can happen--- what if  (say) at the convention Kristi Noem is picked for VP (she is on some lists of possible running mates for Trump) but then after that Trump has a health problem and withdraws and after the dust settles, Haley is VP. So I need to word the bet carefully so that I don't lose in that case. 

3) NOT-Haley is now at 88 cents so I may make more of a profit!

4) Some of my thoughts on Trump's possible running mates come from this article on Nate Silver's website: here.  (ADDED LATER: One of my astute readers left a comment that informed me that it should not be called Nate Silver's website.) 

5) NO-PENCE is selling for 99 cents. I am sure Pence won't be VP in any world, but to make any real money on that you would need to buy A LOT of shares.

6) Tim Scott and Nikki Haley both said they are not interested in the VP job. People running for prez always say that. It has no information value since often they end up on the ticket anyway. Well--- not that often since lately its not that often that a primary opponent is VP. (Kamala Harris was one, but before that you need to go all the way back to 2004 Kerry-Edwards. One of my astute readers points out that Biden ran for prez in 2008, though I didn't count that since he dropped out after the Iowa Caucus where he got less than 1% of the vote. So this depends on what you mean by `running for prez'.) 

7) Winning X dollars will make me feel good. Losing Y dollars will make me feel VERY BAD. So emotionally I shouldn't be betting. And I don't. My non-math friends (I have some!) ask me why  don't go to Las Vegas and clean up, using my knowledge of Ramsey Theory. Um.... The odd thing is that even if I was really good at Probability its still hard to make money in Vegas. As the saying goes: the money you gamble in Vegas, stays in Vegas.

8) I have blogged before about gambling. One theme is that there is no such thing as a sure thing. Here are the links:

Betting on who will win the Superb Owl if one team is undefeated here. (Superb Owl is not a typo, see next link for why I am calling that big football game the Superb Owl.)

Betting on weird things in the Superb Owl: see here

Betting on long shots in the Kentucky Derby: see  here

Betting on VP in 2008: see here

 Betting on Cash Cab: Part of this post here

War Games

With the self-destruction of OpenAI well underway, Friday night I watched the movie War Games for the first time since the 80s. Quick synopsis (spoilers): NORAD can't trust humans to launch nuclear weapons so it creates an AI system to replace them. A pre-Ferris Matthew Broderick both breaks into the system triggering a potential nuclear war and saves the day in the end. 

The movie had great influence for a rather ridiculous story. What Broderick's character did was not a federal crime at the time and the movie led to legislation to fix that. The DEF CON security conference was named after the DEFCON alert levels highlighted in War Games. The movie, which celebrated the male hacker, came out in 1983 at a time we had near parity in genders in computer science that would quickly dissolve.

War Games played up the doomsday scenario of AI, along with earlier films like Colossus: The Forbin Project and Hal in 2001: A Space Odyssey. The dangers of AI might have been at the center of Sam Altman's firing

The departure of Mr. Altman, 38, also drew attention to a rift in the A.I. community between people who believe A.I. is the most important new technology since web browsers and others who worry that moving too fast to develop it could be dangerous. Mr. Sutskever, in particular, was worried that Mr. Altman was too focused on building OpenAI’s business while not paying enough attention to the dangers of A.I.

In the movie a 4-star general states what every movie goer was thinking.

Just unplug the goddamn thing!

The response:

That won't work, General. It would interpret a shutdown as the destruction of NORAD. The computers in the silos would carry out their last instructions. They'd launch.

So I'd unplug the computers in the silos, but that wouldn't have kept the movie going. 

Inverting a Function

With the STOC deadline this last Monday, a number of complexity papers have appeared on arXiV and ECCC. Two caught my eye because they seem to independently prove the same interesting result.

Beating Brute Force for Compression Problems by Shuichi Hirahara, Rahul Ilango and Ryan Williams

The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False by Noam Mazor and Rafael Pass

Suppose you have a function f that maps from \(\Sigma^*\) to \(\Sigma^n\) and runs in time poly(n). Suppose for some x you knew there was a y of length m such that f(y) = x. How hard is it to find y? Standard brute force search would take time \(poly(n)2^m\). With a quantum computer you could find the y in time \(poly(n)2^\frac{m}{2}\) using Grover's algorithm. How about classically?

These papers show that you solve this problem non-uniformly in time \(poly(n)2^\frac{4m}{5}.\) A bit surprising that you can avoid searching the whole space of solutions. Has applications to the minimum circuit-size problem and time-bounded Kolmogorov complexity. Both papers build on earlier work of Amos Fiat and Moni Naor. 

I have no inside knowledge whether these papers were either or both submitted to STOC, but if they were and the program committee finds the results worthy, how will it be handled? Merge or no-merge. We'll find out in mid-February when the committee announces the acceptances.