Saturday, March 26, 2022

I don't care about Ketanji Brown Jackson's LSAT scores and she does not care about my GRE scores

Tucker Carlson has asked to see Ketanji Brown Jacksons's LSATs. 

When I applied to College they (not sure who they are) wanted to see my SAT scores. Putting aside the issue of whether the test means anything, they viewed the SATs (and my HS grades and letters from teachers) as a sign of my 


When I applied to Grad school they (a different they) wanted to see my GRE scores. Putting aside the issue of whether the test means anything, they viewed the GREs (and my college grades and letters from professors) as a sign of my


When I applied for jobs as a professor they (another they) wanted to see my resume (papers I wrote) and letters from my advisor and others (I think). They did not look at my grades (just as well- I got a B in both compiler design and operating systems. Darling is amazed I even took operating systems). This was probably the oddest of the application processes since they were looking for both

                                                    potential and achievement.

That is, the evidence that I could do research was that I had done some research. This was before the current  era where grad students had to have x papers in prestige conferences to get a job at a top y school. The letter from my advisor may well have spoken of my potential. 

When I went up for tenure ALL they cared about was PAPERS (and letters saying they were good papers), and some teaching and service. It was based just  on 


A wise man named Lance Fortnow once told me:

The worst thing a letter of recommendation for a tenure case can say is `this person has great potential'

It would have been rather odd for Tucker Carlson to ask to see my SAT scores or GRE scores or by HS, College, or Grad School grades as a criteria for Tenure. Those tests and those grades are there to measure potential to DO something, whereas if you are going up for tenure or a Supreme Court seat, you've already DONE stuff. 

After I got into grad school one of my first thoughts was

Nobody will ever want to see my GRE's again. ( I was right.) 

After KBJ got into Law School she might have thought

Nobody will ever want to see my LSAT scores again. (She was wrong.)

Sunday, March 20, 2022

Do you want to be the SIGACT NEWS book review editor?

I ran the SIGACT Book Review Column from 1997-2015 (18 years). You can find all of my columns, plus reviews I did for Fred, here.

When I handed it off to Fred Green I gave him this sage advice:

                   Nobody should do this kind of job for more than about 5 years.

He ran the SIGACT Book Review Column since the end of 2015. You can find some of his columns here.

Fred is taking my advice and looking for a successor.

SO, this blog is a call to ask


If so then email


DO NOT BE SHY! I suspect he won't get many applicants, so if you want the job its probably yours.


1) You get to skim lots of books and read some of  them.

2) You get some free books.

3) You get plugged into the book community (this helped me when I wrote my two books).

4) You'll have two Veteran Book Review Editors happy to review for you.

5) You get to decide the direction the column goes in.

Both Fred and I did mostly CS theory books. However:

a) I did more combinatorics, educational, history, and Computers & Society books than usual.

b) Fred did more Number Theory and Physics than usual.

(Since I did the job 18 years and Fred for 6, its not clear what usual means.) 


1) You have to get out a book review column 4 times a year.

2) You have to find reviewers for books and then email them when the reviews are due.

(I think Fred is still waiting for me to review a Biography of Napier. Oh well. On the other hand, I was the one who liked having history books, which may explain why Fred never hassled me about it.) 


Prob should be done by someone who already has Tenure. While seeing and skimming thosebooks is GOOD for your research career, and good in the long-termsomeone pre-tenure really needs to get papers out in the short term. Also, when you get a book think about who might be good to review it--- don't take on to many yourself. 


In a recent column I had a review of a 5-book set from the LESS WRONG blog. I amcurrently working on a review of a 4-book set set from the LESS WRONG blog. This willeither be a parting gift for Fred or a Welcome gift to his successor.

Thursday, March 17, 2022

The War and Math

During the early parts of the cold war of the 20th century, we saw two almost independent developments of computational complexity, in the west and in the then USSR. There was little communication between the two groups, and countless theorems proven twice, most notably the seminal NP-complete papers of Cook and Levin. To understand more, I recommend the two articles about the early days of complexity by Juris Hartmanis and by Boris Trakhtenbrot.

Russia's invasion and relentless bombing in Ukraine have quickly separated the east and the west again. 

Our first concern needs to be with Ukraine and its citizens. We hope for a quick end to this aggression and Ukraine remaining a free and democratic country. Ukrainian cities have undergone massive damage, and even in the best possible outcome it will take years if not decades to fully rebuild the country. 

Terry Tao has been collecting resources for displaced mathematicians due to the crisis.

We've cut off ties with Russia institutions. In our world, major events to be held in Russia, including the International Congress of Mathematics and the Computer Science in Russia conference are being moved online. I was invited to workshops in St Petersburg in 2020 and 2021, both cancelled due to Covid, and was looking forward to one in 2022, which if it happens, will now happen without me. 

The music world has has cancelled some stars, most notably Valery Gergiev and Anna Netrebko, due to their close ties to Putin. It's rare that we do the same to mathematicians for political reasons though not unheard of. I suspect most of our colleagues in Russia oppose the war in Ukraine, or would if they had accurate information of what was going on. I have several Russian friends and colleagues including two I travelled to Moscow in 2019 to honor and would hate to be disconnected from them.

It's way too early to know how this will all play out. Will we see a quick Russian retreat? Not likely. Will we see a situation that sees a mass migration of Ukranian and Russian mathematicians and computer scientists to Europe and North America, like in the 1990's? Possibly. We will see a repeat of the cold war, disconnected internets and science on both sides happening in isolation? I hope not but we can't rule it out.

Tuesday, March 15, 2022

Problem X won't be solved in MY lifetime- but what about...

1) In 1989 on the episde The Royale of Star Trek: The Next Generation (which takes place in the far future)  Captain Picard is working on Fermat's last theorem which he says quite explicitly is still open.

When I saw the episode I asked Larry Washington, a Number Theorist at Univ of MD, when he thought FLT would be solved. He said

                                      It will be solved within the next 10 years.

And indeed- Wiles solved it in 1993-sort of. There was a flaw in the proof which he fixed in 1994 with the help of his former student Richard Taylor. Wiles published the correction to the flaw in 1995, so we will date it as having been solved in 1995. Larry Washington was correct.  And in an episode of Star Trek: Deep Space Nine in 1995 (episode name:Facets) Dax says that a previous host, Tobin Dax, had done the most creative work on FLT since Wiles. Maybe Tobin wrote this limerick:

A challenge for many long ages

Had baffled the savants and sages

Yet at last came the light

Seems that Fermat was right

To the margin add 200 pages.

I asked Larry W when he thought Riemann would be solved. He said  

                    In your lifetime but not in mine.

He is about 10 years older than I am and I think we are both in good health. This seems like a rather precise prediction so I am skeptical. But he did get FLT right...

2) In class I sometimes say things like 

I do not think Quantum Computers will factor faster than classical in my lifetime. 

I do not think P vs NP will be solved in my lifetime.

I can imagine P=BPP will be proven in my lifetime. (I said that 10 years ago. I am less imaginative now.) 

I hope the muffin problem is solved in my lifetime (it was, see here).

I didn't quite think about the difference in my age and the students until recently when I was working with Ilya Hajiaghayi (Mohammd H's 9 year old son) on cryptography and he said 

In your recorded lecture you said you don't think quantum computers will be a threat to cryptography  in your lifetime. What about in my lifetime?

Indeed- his lifetime and mine are rather far apart. 

I am reminded that one of the answers to my P vs NP poll made the point that while we have some sense of what will happen in the next 10 years, maybe even 20, math and life can change so much that conjectures beyond that are guesswork. Any  prediction for x years from now you should have confidence < 1/ln(x) of it being true.

Sunday, March 06, 2022

Random thoughts on the Russian Invasion of Ukraine

 1) My first thought was: Doesn't Putin know that his army (and his society) is corrupt and people are promoted on loyalty rather than talent, hence the invasion is not going to work? But then note

a) He invaded Georgia (the country not the state)

b) He annexed Crimea

c) NATO agreeing on sanctions? They can't even agree on what to have for lunch.  

d) The above question ASSUMES that he will lose. This is not clear yet.

2) The US and other countries are imposing sanctions. Visa, MC, and Netflix have withdrawn from Russia. Will these cause Putin to stop, or will they just impose hardships on the citizens without having an affect? I ask non-rhetorically. Foreign Policy is hard, though I suspect Biden has hired experts and is listening to them. Doesn't mean they are right. 

3) This seems like a case where its obvious that Putin is in the wrong so I was surprised to see some Pro-Putin arguments. To be fair, some were more that we should not get involved, which is not quite Pro Putin. Here are some and my thoughts on them.

a) Putin never called me a racist and never made my kids learn Critical Race Theory. This is meant as a GOTCHA comment. To take it seriously one would have to (1) examine what American's are learning in grade school, (2) examine what Russians are learning in grade school, (3) see which country is giving their students a more honest view of things (particularly history), and (4) decide that whichever school is teaching more honest material deserves are support. 

b) Putin is a strong leader and I admire strong leaders. Really? If  Biden was a strong leader who could push through the Build-Back-Better plan, would you admire that? You can't just admire strong leaders in the abstract, you have to see where they lead. (Same with admiring people who have principles.)

c) Putin stands for good Christian values. OH- so Putin likes to help the poor and does not approve of divorce or pre-marital sex. Oh, that NOT what you mean? Oh, you just mean that he does not like gay people or abortion. OH, thats not correct- Russia has the second most number of abortions of any country (see here) So the only issue where Russia shares your values is in not liking gay people. Is that enough  commonality is enough to justify invading a country? This does raise the serious question: who do you support in a war? The country that shrares your values? The country that didn't start it (sometimes hard to tell, though not in this case)? The country you have a treaty with? These are good and serious questions. 

d) How come the world does not like Putin's war based on lies and had no problem with W's war on Iraq that was based on lies? This is actually a good question. Being an academic by first impulse is to write a paper on it. There are differences between the invasion of Ukraine and Gulf War II, but still, lets assume that they really are somewhat equivalent. The person asking the question was probably AGAINST Gulf War II. Hence they should be against the invasion of Ukraine as well. So this is a good question about the America and NATO's Double standard and hypocrisy but is not a reason to be pro-Putin. (I was emailed that there are many conflicts that American and NATO do not care about that are as bad as Putin's invasion.) 

e) Russia had real concerns about security. The last time Russia was invaded was WW II (if I am wrong then please correct me in the comments). Even so, I've heard analogies made to America freaking out when Cuba had Nuclear missiles. There were no nukes in Ukraine. Ukraine was not going to join NATO anytime soon. I wonder if this was a pretense on Putin's part and not a real reason. 

f) See here. I give an excerpt (I am not making this up). 

But as its Covid mission has become less clear, the group’s channels have turned to Russia’s invasion of Ukraine, where conspiracy-minded thinking has flourished. While some group members have admonished Russian President Vladimir Putin for the invasion, QAnon and anti-vaccine contingents within the groups have seized on a false conspiracy theory that the war is a cover for a military operation backed by former President Donald Trump in Ukraine.

The conspiracy theory, which is baseless and has roots in QAnon mythology, alleges that Trump and Putin are secretly working together to stop bioweapons from being made by Dr. Anthony Fauci in Ukraine and that shelling in Ukraine has targeted the secret laboratories. Fauci, director of the National Institute of Allergy and Infectious Diseases, has emerged in the past year as a main target for far-right conspiracy theories.

3) I was somewhat surprised when Hungary came out against Putin. But Putin's arrangments with his allies are transactional- there is no real love there. I was much more surprised when Switzerland came out against Putin. Switzerland has been neutral since 1515 (I think I read that some place). 

Wednesday, March 02, 2022

REU programs in general, and two at Univ of MD this summer.

REU stands for Research Experience for Undergraduates. 

REU programs are funded by the NSF. The NSF website of REU programs is here

Univ if MD at College Park dept of Comp Sci is running two REU programs this summer:

I (William Gasarch) am running  REU-CAAR (Combinatorics and AI Applied to Real problems) whose theme is applying theory to practice. The website for it is here.

 Jacquelyn Michaelis and Mihai Pop are running REU-BRIDGe (Bioinformatics Research In Data science for Genomics) which, as you can probably tell from the name, is in bio-comp. The website for it is here.

Most REU programs have the following: 

1) There is an admissions period where many people apply (I had around 200 applicants last year) of which only about 10 get in. Some have money for a few extra students. This year both REU-CAAR and REU-BRIDGe have applications due March 22; however, in the past I have admitted students before then, so students who apply March 21 may be at a severe disadvantage. 

2) Students apply from across the United states and these programs are competitive, so good to apply to several that you would definitely goto. Students ask me how many- I'll say 10 though temper that with only applying to those you REALLY would goto, and if there are MORE THAN 10 that look awesome, you could apply to more. 

3) Students stay in the dorms (the last two years some programs cancelled, and some were virtual- mine was virtual) and get stipend of $6000, and a meal card. The program is 10 weeks.

4) Students work on projects in teams of 2-5. Some programs have the students pick what projects they would be happy to work on when they apply (mine does that) while others assign projects once students arrive (REU-BRIDGe will do that). The later makes sense if the program is very focused so the projects do not differ that much. 

5) These programs are excellent for giving ugrads a chance to do research (NSF wants at least half of the students to come from non-research schools) and a sense of what grad school is like. So I recommend students thinking of grad school, or just want to do research, to apply to these programs. 

6) Some students get papers out of the research. In these cases the research usually continues after the program is over. 

7) It is healthy for a student to go to an REU program that is at a DIFFERENT school then where they are an ugrad for broadening. There may be mitigating circumstances where this is not possible.