PDQ Shor (?-2025)

PDQ Shor

PDQ Shor, Peter Shor's smarter brother, passed away last week. PDQ was a Physicist/Computer Scientist/Mathematician/Astrologer/Psychic at the University of Northern South Dakota in Wakpala.

Dr. Phineas Dominic Quincy Shor III, PhD, MBA, BLT, received his education at Europa U. during one of his many alien abductions. He ended up in South Dakota after having fled every other state.

He was most famous for the concept of unnatural proofs, collected in his anthology Proofs from the Other Book, which includes his classic "interpretive dance proof" of the Pythagorean theorem. Critics complain the proof only handles the case where the right angle is on the left.

His follow up book, Proofs from the Crypt, contains his masterpiece, a 1237 page proof that conclusively shows that the empty set contains no irrational numbers.

Like his brother he's moved to the quantum space, reverse engineering Peter's work by giving a doubly exponential time quantum algorithm for multiplying numbers. He created the innovative dipping bird quantum error collection machine that constantly monitors a quantum machine collapsing all entanglement. Apple bought the device for $327 million which immediately destroyed their plans for a QiPhone.

PDQ used the proceeds to create the perpetual Turing machine, guaranteed to never halt. Until it did.

Sadly PDQ passed away from paranormal causes last week. Or was it last year? No one is quite sure. He donated his body to pseudoscience, currently lying in state in an undisclosed state. We hardly knew you.

With apologies to Peter Schickele. This April Fools post was inspired by the complexity class PDQMA.

Survey's are done stupidly/A stupid question from a survey

 I have often began taking a survey and quit in the middle. Why?

1) It goes on to long. When I told the surveyors that he may get more people quitting for that reason so he should make it shorter he said, rather rudely, that he is an expert on surveys and they need to ask this many questions to calibrate things properly. I tried to engage him in an intelligent conversation about the tradeoff: the longer it is the better the info, but less people fill it out, so what is the optimal point? He told me I was an idiot. Well... that's not going to encourage me to fill out his survey.

2) It asks questions that are too personal. 

3) It asks questions that seem irrelevant to me for their purpose (to be fair, perhaps I do not know the real purpose)

4) They ask a really stupid question. Here is the stupidest I've seen:

Challenge: Have you ever seen a stupider question? 

As always, I ask non rhetorically. 

What Happened to MOOCS?

In 2012 I wrote a blog post about the growing influence of Massively Open Online Courses, or MOOCs.

John Hennessey, president of Stanford, gave the CRA keynote address arguing that MOOCs will save universities. He puts the untenable costs of universities at personnel costs (faculty salaries) are making colleges unaffordable (not sure I fully agree). He argued that MOOCs will help teach courses more effectively. The hidden subtext: fewer professors and probably fewer universities, or as someone joked, we'll all be branch campuses of Stanford.

I ended the post "MOOCs may completely change higher education in America and around the world. Or they won't." A reader asked "Wondering what are you takes about MOOCS now?". Good question.

If you want a detailed answer I had chatty put together a deep research report. Here's my take, mostly from the US computing perspective. The term MOOC is rarely used anymore, but we have seen tremendous growth in online courses and degrees, particularly in Masters programs.

We've seen some major successes, most notably the Georgia Tech Online Masters of Science in Computer Science program that we started in 2014. By we, I mostly mean then-dean Zvi Galil's tenacity to make it happen. Zvi made the right moves (after some pushing), getting faculty buy-in, strong incentives for faculty participation, putting significant resources for course development, a very low-cost degree and most importantly insisting that we have the same if not better quality than our on-campus offerings. The program grew tremendously reaching about 10,000 students by 2020. Georgia Tech had to add a new graduation ceremony for students who finished the degree remotely but traveled to campus for graduation.

We've seen a plethora of new programs. Most domestic students can get a good computing masters degree at a fraction of a cost of an in-person program. On-campus Masters program in computing are now almost entirely international for on-campus programs can deliver something an on-line course cannot: A visa, and a chance to build a life in the United States.

These new programs vary quite a bit in quality, some truly strong, others less so. Some are outright misleading, making a deal with a university to use their name but otherwise having no connection to the school's faculty or academic departments. These programs often feature 'professional certificates' marketed under university branding but are actually developed and administered by third-party education companies.

While we learned to teach everything online during the pandemic, on-line degrees don't work as well for bachelor degrees where the on-campus experience almost matters more than the courses, or for research-intensive PhD programs.

We are not all branch campuses of Stanford but the story isn't done. Colleges continue to have financial challenges, artificial intelligence will continue to play new roles in education, not to mention the recent actions of the Trump administration. Hopefully MOOCs won't be the only thing surviving.

Recording lectures? Posting the Recordings? Using Slides?

The issue of whether to record lectures or post slides or more generally how much material to give to the students is a new question (the last 20 years?) but I do have an anecdote from 1978.

I was taking an applied math course on Mathematical Modelling from James C Frauenthal (He would sometimes write his initials \(\binom{J}{F}\)) and he passed out his notes ahead of time. I think I was the only student who read them ahead of time. One time I had read the following passage ahead of time:

We have been somewhat cavalier in our assumptions.

During class he said

What is wrong with this mathematical model? 

I replied

We have been somewhat cavalier in our assumptions.

He was somewhat surprised, but pleased that someone was reading his notes. 

FAST FORWARD TO MODERN DAY.

 

How much material should we make available for our students? I post slides and recordings. 

PRO: If a student misses class they can catch up. Especially good if missing class is rare.

PRO: If a student is in class then they can go back to some point they were confused on.  

PRO for slides: When asking a student when they began getting lost we can find the exact slide. This is much better than the word salad that students sometimes emit when describing where they are lost.

BILL: So you understood the definition of P. So you were lost when I defined NP? 

STUDENT: No, I got lost when you described some kind of really exciting algorithm.

BILL: Exciting algorithm? What did it do?

STUDENT: You said it was a paradox.

BILL: This is a class in algorithms. We have not discussed any paradoxes.

STUDENT: Did so!

BILL: We can figure out what ails thee. What did the algorithm do?

STUDENT: Something about the whole being greater than the sum of its parts.

BILL: Parts! I think you mean that we solve sub parts and then put them together. This is the Dynamic Programming paradigm. OH- I think you confused  paradigm and paradox.

STUDENT:  That's exactly what I said. Dynamic means exciting! And paradox is just another name for paradigm.

Often it was hard to see where they got lost.  

CON: Students may skip class and not go over the slides or recordings!

CON: The technology sometimes does not work.

BILL: You missed class and expect me to redo the lecture in my office. Did you watch the recording?

STUDENT: No. The recording did not work and it's your fault!

BILL:  The first day of class I said you should come to class for the following reasons

1) You can ask questions. The paradox is that's hard to do in a large class, but with so many student cutting class, it's a small class!

2)  Taking notes is a good way to solidify knowledge.

3) Going to class forces you to keep up.

4) The technology might not work. Last semester this happened four times. Twice it was my fault, and twice is was not my fault. But that does not matter- it will happen. 

5) If  you show up in my office hours and want me to explain  what I lectured on I will be annoyed.

STUDENT: Uh,... I missed the first day.

CON: In the long term students get in the habit of not going to class.  I can't tell if this is worse than it used to be. 

CON for Slides: Its hard to be spontaneous. Some of the classrooms don't even have whiteboards to go off-script with. The following happened in the pre-slide days (apologies- I've told this story before on this  blog) on April 25, 2003 in my Automata Theory class. I had already done decidability and was going to do r.e. sets.

STUDENT: Do you know whose 100th birthday it is today?

BILL: Will there be cake? If so will they let me eat cake?

STUDENT: Today is Kolmogorov's 100th birthday.

BILL: AH! I was going to do r.e. sets but instead I will do Kolmogorov Complexity!

STUDENT: Great! Uh. Maybe. Is it hard? 

BILL: Its fun!

I then gave a lecture on Kolmogorov complexity on the fly, on the whiteboard. I made it part of the course and on the final I asked them to show that if  w is a K-random string of length n then any context free grammar for {w} in Chomsky Normal Form requires at least \( n^{0.99} \) rules (this is not the strongest result possible). 

This is impossible with slides. No more on-the-fly lectures. 

CON for slides: Some proofs are impossible to do on slides. The Poly VDW theorem and the Kruskal Tree Theorem are two of them. Fortunately those are both in Ramsey Theory that has 30 students and a whiteboard, so for those lectures I use a white board. 

PRO for slides: My handwriting isn't that good, so slides helps a great deal.

CAVEAT: I used to read a proof, write it out by hand, type it up in LaTeX, and then make  slides.  Now I go straight from reading it to slides. This is sometimes not a good idea as I am worrying about fonts and  formatting before I really understand the proof. I recently went BACK to the handwritten notes  THEN LaTeX THEN slides. That increased my understanding since (1) when doing the handwritten notes I was not distracted by fonts or formatting, and (2) at every iteration I picked up some subtle point I had missed. 

CAVEAT: When teaching a large class you really can't use the whiteboard since the people in the back row can't see. I don't know if that's an argument FOR slides or AGAINST large classes. 

SO- what do you do: record, not record, slides, no slides.And why? And does it work? 

 

A Failure to Communicate

With care you can explain major ideas and results in computational complexity to the general public, like the P v NP problem, zero-knowledge proofs, the PCP theorem and Shor's factoring algorithms in a way that a curious non-scientist can find interesting. Quanta magazine keeps coming back to complexity. because we have a inherently interesting field.

So why am I having such a difficult time with the new Ryan Williams result, that time can be simulated in nearly quadratically less memory, or more precisely DTIME(\(t(n)\)) \(\subseteq\) DSPACE(\(\sqrt{t(n)\log t(n)}\)), based on the Cook-Mertz space-efficient tree evaluation algorithm.

Many results in complexity are quite specialized and technical but this shouldn't be one of them. Ryan's result involves a major new relationship between time and memory, the two most basic resource measures that goes back to the 1960s. Everybody understands time--waiting while their computer or phone is spinning. They know about memory, at least that you have to pay more for an iPhone with more of it. Yet still I'm challenged to explain this result.

Maybe because for historical reasons we use SPACE instead of MEMORY, or the pesky \(\log t(n)\) factor. Someone said they got lost in the logarithms. But we can talk about the gist of the result without mention space or logarithms.

It might be the \(t(n)\). We take for granted that we measure resources as a function of the problem size but outsiders could find it a challenging concept. For P v NP I just talk about efficient computation, here you can't avoid more specific running times. 

Or maybe people don't think about time and memory. Most operations on a computer happen close to instantaneously. Nobody thinks about memory unless they run out of it. 

Or because we don't have good real-world examples. When would you prefer a space \(\sqrt{t(n)}\) time \(2^\sqrt{t(n)}\) procedure to a space \(t(n)\) time \(t(n)\) algorithm? 

AI is supposed to be good at this. OK, Claude take it away.

Ryan Williams' breakthrough paper shows that computers can solve complex problems using far less memory than previously thought possible. For 50 years, computer scientists believed that problems requiring a certain amount of time (t) needed at least t divided by a small factor of memory. Williams proved that these same problems can actually be solved using only about the square root of t memory. He achieved this by connecting these problems to the Tree Evaluation problem and leveraging a recent algorithm by Cook and Mertz. This result makes significant progress toward resolving the longstanding P versus PSPACE problem, suggesting that many algorithms could potentially run efficiently on devices with much less memory than we currently use.

Imagine a navigation app trying to find the optimal route through a complex city network. Before this discovery, engineers believed that calculating detailed routes required either substantial memory or accepting slower performance on memory-limited devices. Williams' theorem suggests these calculations could run using dramatically less memory—potentially reducing requirements from 100 MB to just 10 KB (roughly the square root). This breakthrough could enable sophisticated navigation features on devices with severe memory constraints, such as smart watches, older phones, or embedded car systems, allowing them to handle complex routing problems with multiple stops or constraints without performance degradation.

My Post-Covid Post

 I had been meaning to write a post-COVID post for a while, but

a) Are we finally post COVID? (I think so)

b) Are the long term affects of  COVID (society not health) known yet?

However, Lance wrote a post-COVID post (see here) which inspired me to do the same. 

Random Thoughts on COVID

1) COVID probably helped Biden win the 2020 election. If Harris  had won in 2024 then Biden winning in 2020 would have been a bigger change. 

2)  VAX-skepticism is now mainstream. This had not been a partisan issue before COVID though there were some people against vaccines. Oddly enough I think mostly on the far left: a back-to-nature thing. And VAX-skepticism has gone beyond COVID- some states are letting people NOT get vaccinated which has already caused a measles epidemic.

3)  I used to get more work done at school. Now I get more work done at home. COVID forced me to enter the 21st century.

4) People come into school less often.  There are faculty whose tenure cases I will vote on who I never met. To be fair, we do have a big department so (a general theme) COVID accelerated some trends that were already there.

5) Office buildings are less full as more people work from home. I've read that this may cause an economic crisis with people who borrowed money to build NEW office buildings. There are some plans to convert office building into residential, but that seems harder than it sounds.

6) My favorite place to have lunch, THE FOOD FACTORY closed down!

7) I used to mentor around 10 HS students a year (some of the Magnet schools in the area have a research requirement-though the students mostly ARE good and ARE NOT just there for the requirement).  It was a logistical issue to get them or their parents parking passes (also an issue of what their parents DO while I am teaching their kids Ramsey Theory). Now I do most of my mentoring on zoom. I mentored 32 in 2024 (in groups- so it was not 32 projects).

8) I can now hold extra office hours at night on zoom. 

9) Before COVID I was slowly switching from whiteboard to slides since I was recording lectures and my handwriting is not very good. Now MY ENTIRE COURSE is on slides. Clyde Kruskal points out:

 If your entire course is on slides then either  your slides are too dense or your course is too shallow.

He may have a point there. However,  in a small class I sometimes DO go to the whiteboard. I did it this semester in my Ramsey Theory course when I taught the Kruskal Tree Theorem (the set of trees under minor ordering is a well quasi order-by Joe Kruskal, Clyde's Uncle).

10) This is a bigger issue- is technology driving what topics we cover? 

11) COVID --> classes recorded and  slides that are available --> student attendance is down. Is this bad? Depends. If the students who don't show up actually keep up, its fine. If they hunt and peck through the slides so they can do the HW, that's bad. COVID might not have caused this problem,but it  accelerated it. The question of Post/Record or Not is an issue for a later blog. Pesonally,  I post and record.

12) School children who had to learn at home, probably bad for their future education.

13) Chem labs and Physics labs---do we have a class of chemists who did less lab work?

14) Some couples had to spend more time with each other than usual. This could be good or bad (for me it was good).

15) Some scenes on the TV show Monk (about an OCD Detective) now seem normal- like wiping off doors for germs.

16) Wearing masks in public is not considered weird.  It has gone back to being unusual, but it has not gone back to being weird. I know someone who found that by wearing one he does not get ordinary colds so he keeps wearing it.

17) By around May of 2020 there were about 100 or more novelty songs about COVID. I compiled a website of what I considered the best ones. Its part of my website of novelty songs, here. The three best IMHO are here, here, here.  OH- while getting those linked I found another awesome one: here

18) Some of the working-at-home or meetings-on-zoom was because of COVID. And some is technology (zoom). But some is sociological. Here is an example:

DARLING (on a Sunday in 2018): Bill, my back hurts and I don't think I should drive today, but I want to go to church. So... what  can we do?

BILL: Uh-OH, I think our church streams its service.

DARLING: Well pierce my ears and call me drafty! You're right! I remember that now. Great! You are my brilliant Bill!

BILL: And you are my darling Darling!

(We watched the service online and it was fine.)

 Suffice to say, thinking of going to church online would not take a brilliant Bill now. 

19) There is a down side: Meetings online, church on line, classes on line, one can get more distracted.

20) Faculty meetings are hybrid and I usually go on zoom. The Math dept has said that you HAVE TO GO in order to vote. They are NOT being Luddites- they see the value of in-person meetings. I do not know who is right.

If the meeting is on zoom more people are at the meeting.

If the meeting is in person then less people come but they are paying more attention. Or are they? People can be in person and still tune out, see here.

In the past someone could say I'll be out of town so I can't go to that meeting. That may be less of an excuse in the future. Maybe even now.

21) One of my wife's relatives died of COVID (before vaccines were available) and one of my friends lost his sense of smell because of COVID (before vaccines)

22) Some TV shows incorporated COVID into their story lines. For some the order a show is shot is different than the order they are shown, so you could have one with people wearing masks and COVID being in the background, and the next week nothing about COVID.  

23) I managed to still run my REU program - virtually- in summer 2020 and summer 2021. The research was as good as normal, and I could admit more students since I was not paying for housing, but the students had a much worse time because of the lack of social activities-- we did have some online but its really not the same.  (As for my REU program in Summer 2025-- there are other issues that I will discuss in a later blog post.) 

24) I used to see Lance about once a year when he came to Washington DC either on chairman-business or Dean-business, or NSF-business. I have not seen him in person since... hmm, I do not know. Might be since before COVID. I do see him on zoom once in a while. And whenever a theorist dies he gives me a call to discuss the blog-obit.

25) I am a homebody- I can stay at home for many days in a row. I watch TV, go on treadmill,  and watch TV  while on treadmill. I also  surf the web, read papers, think brilliant thoughts, and  make up slides. Other people feel a  need to GET OUTSIDE THE HOUSE. 

 26) My book club and my game night have both moved online and have not resumed being in person.

book club: Two of the people in it moved to Georgia so we thought we would not see them anymore. But then COVID hit and it's just so much easier for them and everyone else to have book club on zoom.This works pretty well. 

game night: One person is still COVID-shy (this may be reasonable in her case) hence does not want to go to gatherings. And during COVID 2 people from OUT OF STATE joined the game night.  So now it is always on line. This does LIMIT which games we can play, and some games are not as good online. 

27) Since Darling and I stayed at home so much we got out of the habit of putting our wedding rings on before leaving the house. We still have not gotten back in the habit. This may be the least important long-term effect of COVID.

28) (ADDED LATER INSPIRED BY A COMMENT) One of the comments asked (though assumed yes) that I am back to living a normal live. Thats mostly true except for the following:

I am VERY CAREFUL to not injure myself (e.g., no more jogging outside where a crack in the sidewalk could make your break a bone) because of wait times in hospitals during COVID- but it seemed like a good idea even post-COVID (if we are indeed post-COVID- the commenter challenges that). 

I do mask when I go shopping.

I test if I have symptoms (I had a mild case once.)

I get the flu vaccine- I didn't use to- but I got it since I didn't want to get the flu and THINK it was COVID.

Some of my friends and relatives don't eat in resturants anymore, or insiste I test before coming over, or... and I HAPPILY accomodate them.

The COMMENT is very good and I recommend everyone read it.

 

 

Covid and Complexity

As we hit five years from when the world shut down, lots of discussions on how Covid has changed society. What about academia and computer science?

It's a challenging question to ask as Covid is not the only major change in the last five years. We've seen wars in Ukraine and Gaza and a huge political changes around the world. We've had major technological changes as well, most notably the rise of machine learning, particularly large-language models. 

But Covid changed us quickly, moving immediately to online teaching, meetings and conferences. Both my children move in with us for six-months. Crowded but it was great to spend time together. 

Most of us have moved on from Covid, though a small number still take it seriously, avoiding crowded areas, wearing masks, not eating indoors at restaurants, even still isolating. We need to all respect everyone's individual risk decisions when it comes to the disease. And we should never forget the many we've lost to the disease. 

We saw many attempts at virtual and later hybrid conferences but none worked particularly well, despite some valiant efforts. There's just a limit to how long you can be engaged staring at a screen. The best we have now are recorded talks with a watch party, and a separate in-person meeting. Not just for Covid, but because international travel has become more difficult for many.

By necessity we saw a vast improvement in online collaboration tools, at least until Google killed Jamboard. With papers generally available online, there is very little you can do in your office you can't do at home. So we see less people come into work every day, faculty, students and staff. Collaborating with someone across an ocean is almost as easy as collaborating with someone at your university. I find new faculty feel less need to choose a university for its resources and colleagues than for its location.

Personally I try to avoid virtual meetings as much as I can, which is not nearly enough. I have a student I work with at another university in Chicago who prefers to make the long trek here to talk research than meet on zoom, as we are much more productive that way. Others seem to prefer and even thrive on online meetings. Each to their own. 

The students have suffered the worst from Covid especially those who lost a year or more of in-class pre-college education. We see some incoming students struggling more both from a knowledge background but also a social one, with many just watching their lectures online or not fully engaging if they come in person. It will take a whole generation before we fully recover as a society from that disease.

Numbers that look prime but aren't

 
A long time ago I made up the question (are questions ever really made up?)

What is the least number that looks prime but isn't?

It was not quite a joke in that it has an answer despite being non-rigorous.

My answer is 91:

Dividing by 2,3,5,11 have TRICKS

Squares are well known.

So the first number that looks prime but isn't is \(7\times 13=91.\)

I recently  saw the question asked on Quora and given a more interesting answer. The answer is by Nathan Nannon, a PhD in Math at Univ of CA, Davis (Graduated 2021). I paraphrase it here and then have some questions.

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

What does it mean to look prime?

FIRST CRITERION: 

1) Its decimal representation ends in 1 , 3 , 7 , or 9 , and

2) It is not on the multiplication tables that a lot of people memorize, which go up to 12.

Based on these criteria, 39 is the first composite number that looks prime.

(If people no longer learn the mult tables then the answer would be 21.) 

SECOND CRITERION: Use the trick that a number is divided by 3 if the sum of the digits is divisible by 3.  Then the first composite number that looks prime is 91 , followed by 119 , 133 , and 143.

THIRD CRITERION: Fermat's Test: If \(p\) is prime then for all \(a\), \(a^p\equiv a \pmod p\).
Numbers that pass this test and yet are composite are called Carmichael numbers.

Here are the first few  Carmichael number:

561 AH- that does not count since 5+6+1 is divisible by 3.

1105 AH-doesn't count, ends with 5.

1729 AH- Nathan Nannon points out that 1729 is the sum of two cubes (more on that later) and hence we can use \(a^3+b^3 = (a+b)(a^2-ab+b^2)\). This only works if you KNOW that 1729 is the sum of two cubes. AH- most mathematicians do know this because (1) it is the least number that can be written as the sum of 2 cubes in 2 diff ways, and (2) this fact has been popularized by the following true story (I quote from Wikipedia, see here) which explains why such numbers are called Taxicab Numbers

The name is derived from a conversation ca. 1919 involving mathematicians G. H. Hardy and Srinivasa Ramanujan. As told by Hardy:

I remember once going to see him [Ramanujan] when he was lying ill at Putney. I had ridden in taxi-cab No. 1729, and remarked that the number seemed to be rather a dull one, and that I hoped it was not an unfavourable omen. "No," he replied, "it is a very interesting number; it is the smallest number expressible as the sum of two cubes in two different ways."

Note 

1) Oddly enough, the fact that 1729 is the sum of two cubes in TWO diff ways does not make it any easier to factor. We just needed one way. 

2) To say that 1729  does NOT look prime depends on history as well as math. If not for the Hardy-Ramanujan story, would most mathematicians know that 1729 is the sum of 2 cubes. Possibly since its 1000+729. But not clear. Martians may think 1729 looks prime.

2465 AH-doesn't count, ends with 5

2821 AH- just looking at it, it is clearly divisible by 7.

6601 AH- OKAY, this one really does look prime.

UPSHOT
Depending on what criteria you use, the least number that looks prime but isn't is either 21 OR 39 OR  91 OR  6601 or something else, depending on what looks prime to you.

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

QUESTION
Is there some natural and simple criteria that rules out 6601? This may depend on your definitions of natural and simple.

QUESTION The first few Carmichael numbers had small factors. 6601 is divided by 7. Is there some function   f with \(f(n) \ll \sqrt n\) such that if \(n\) is a Carmichael number then it has a factor \(< f(n)\). ?

The next few Carmichael number after 6601 is 8911, which 7 divides. So that looks good. But alas, Jack Chernick proved (see here) that any number of the form \((6k+1)(12k+1)(18k+1)\) where \(6k+1\),\(12k+1\), and \(18k+1\) are all primes, is a Carmichael number. It is not know if this generates infinitely many Carmichael numbers. Hence if some f(n) exists then its probably \(\Omega(n^{1/3})\).