Sunday, June 26, 2022

Counting the Number of 3-colorings of a graph is Sharp-P complete. This should be better known.

BILL: Lance, is #3COL #P complete? (#3COL is: Given a graph G, return the number of  different 3-colorings it has.) 

LANCE: Surely you know that for all natural A,  #A is #P complete. 

BILL: There is no rigorous way to define natural. (I have several blog posts on this.) 

LANCE: Surely then for all the NP-complete problems in Garey & Johson.

BILL:  I know that. But is there a proof that 3COL is #P Complete? I saw a paper that claimed the standard proof that 3-COL is NPC works, but alas, it does not. And stop calling me Shirley.


LANCE: I found this cool construction of an OR gate that creates a unique coloring.


LANCE: That didn't work because you need to take an OR of three variables. OK, this isn't that easy.


LANCE: I found an unpublished paper (its not even in DBLP) that shows #3-COL is  #P complete using a reduction from NAE-3SAT, see here. The proof was harder than I thought it would be. 

BILL: Great! I'll post about it and give the link, since this should be better known. 


This leads to a question I asked about 2 years ago on the blog (see here) so I will be brief and urge you to read that post.

a) Is every natural NPC problem also #P-complete. Surely yes though this statement is impossible to make rigorous. 

b) Is there some well defined class LANCE of LOTS of  NPC problems and a theorem saying that for every A in LANCE,  #A is #P complete? The last time I blogged about this (see above pointer) a comment pointed me to a cs stack exchange here that pointed to an article by Noam Levine, here which has a theorem which is not quite what I want but is interesting. Applying it to 3COL it says that there is a NTM poly time M that accepts 3COL and #M is #P-complete. 
Not just 3COL but many problems. 

c) Is there some reasonable hardness assumption H such that from H one can show there is a set A that is NP-complete that is NOT #P-complete? (The set A will be contrived.) 

Sunday, June 19, 2022

Guest post by Prahalad Rajkumar: advice for grad students

I suspect that Lance and/or I have had blogs giving advice to grad students. I won't point to any particular posts since that's a hard thing to search for. However, they were all written WAY AFTER Lance and I actually were grad students. Recently a former grad student at UMCP, Prahalad Rajkumar, emailed me that he wanted to do a post about advice for grad students. Since he has graduated more recently (Master degree in CS, topic was Monte Carlo Techniques, in 2009, then a job as a programmer-analyst) his advice may be better, or at least different, than ours was.

Here is his guest post with an occasional comment by me embedded in it. 


 I Made this Fatal Mistake when I Joined a Graduate Program at Maryland

Getting accepted to a graduate program in a good school is an honor.

It is also an opportunity to do quality work and hone your skills. I made one fatal mistake at the start of my master’s degree at the University of Maryland which took me down a vicious rabbit hole. I believed that I was not cut out for this program.

The Only Person Who Gave an Incorrect Answer

Before the start of my graduate studies, there was an informal gathering held for newer students and some faculty members. A faculty member asked a basic algorithm question.

Everyone in the room gave one answer. I gave another answer.

This is real life and not Good Will Hunting, and of course, I was wrong. I had misunderstood the question. It would have been a simple matter to shrug and move forward. But the paternal voice in my head saw a good opportunity to continue to convince me that I was an imposter who did not belong here.

Who is Smarter than Whom?

Some of my fellow incoming graduate students, who TAed with me for Bill Gasarch’s class, played an innocent looking game.

“That guy is so smart”.

“I wish I were as smart as her”.

They couldn’t know that this would affect me. I too did not know that this could affect me. But it did. I asked myself “Am I smarter than person X?”. Each time, the paternal voice in my head was quick to answer “No”. And each time I took this “No” seriously.

NOTE FROM BILL: Professors also play who is smarter than who game and we shouldn't.

I Didn’t Choose My Classes Wisely

I made a few mistakes in choosing my classes. I chose Concrete Complexity with Bill, which I later realized I had no aptitude for. I chose an undergraduate class taught by a professor whose style did not resonate with me. Mercifully, I chose a third class that I liked and excelled in. A class which did not destroy my confidence.

In retrospect, though I chose a couple of classes that were not my cup of tea, I compounded my problems with the stories I told myself. I had several good options available to me. I could redouble my efforts in the said classes and give it my best shot. I could accept my inevitable “B” grades in these classes, and be mindful to choose better classes in the upcoming semesters.

I, however, did the one thing I should not have done: I further convinced myself that I was not cut out to be a graduate student.

NOTE FROM BILL: Some students wisely ask around to find out who is a good teacher? Prahalad points out that this is just the first question. A class may be appropriate for you or not based on many factors, not just if the instructor is a good teacher. 

I Fell Victim to Impostor Syndrome

I kept compounding my woes in my second and third semesters. Things got bad -- I took up a position as a research assistant in my third semester. My confidence was low -- and I struggled to do basic tasks that fall under my areas of competence.

In my fourth semester, I convinced myself that I could not code. In a class project where I had to do some coding as a part of a group project, I struggled to write a single line of code.

When I confessed this to one of my group members, he got me out of my head. He got me to code my part more than capably. I’ve written about this experience here.

 It Does Not Matter in the Slightest

I wish I could tell the 2007 version of myself the following: It doesn’t matter who is smarter than whom. In any way whatsoever. We are on our individual journeys. In graduate school. In life.

Comparing myself with another person is as productive as playing several hours of angry birds.

 The Admission Committee Believed in Me.

There was one good reason I should have rejected the thought that I did not belong in the program. The admission committee believed that I belonged here. Consisting of several brilliant minds. If they thought I should be here, why should I second guess them?

NOTE FROM BILL: While the Admissions committee DID believe in Prahalad and was CORRECT in this, I would not call the committee brilliant. As is well known, the IQ of a committee is the IQ of its dumbest member divided by the number of people on the committee. 

Bill Gasarch’s Secret Sauce

Since I took a class with Bill and TAed for him, I had occasion to spend a lot of time with Bill.
In one conversation, Bill told me something profound. He told me the secret sauce behind his accomplishments. No, it was not talent. It was his willingness to work as hard as it takes.
And working hard is a superpower which is available to anyone who is inclined to invoke it. I wish I had.

BILL COMMENT: The notion that hard work is important is of course old. I wonder how old. One of the best expressions of this that I read was in a book Myths of Innovation which said (a) Great ideas are over rated, (b) hard work and follow through are underrated. There are more sources on this notion in the next part of Prahalad's post. (Side Note- I got the book at the Borders Books Going Out of Business Sale. Maybe they should have read it.) 

Talent is Overrated.

I read a few books in the last couple of years that discussed the subject of mastery: Mastery by Robert Greene, Peak by Anders Ericsson, Talent is Overrated by Geoff Colvin, The Talent Code by Daniel Coyle, Grit by Angela Duckworth, Mindset by Carol Dweck

There was one point that all of these books made: talent is not the factor which determines a person’s success. Their work ethic, their willingness to do what it takes, and several hours of deliberate practice is the secret of success. Of course, talent plays a part -- you can’t be 5’1 and hope to be better than Michael Jordan. But in the graduate school setting, where a majority are competent, it really is a matter of putting in the effort.

 Follow the Process

Bill Walsh signed up as the coach of the languishing 49ers football team. The title of his bestselling book describes his coaching philosophy: The Score Takes Care of Itself. He established processes. Focusing on the smallest of details. Walsh made everyone in the football team and in the administrative departments follow their respective processes. Long story short: the score took care of itself. The 49ers won 3 super bowls among other impressive performances.

If I had to do it all again: I would get out of my head. And keep going with a disciplined work ethic. Establish a process. Follow the process. And let the results take care of themselves.

All’s Well That Ends Well

I grinded and hustled and successfully completed my Masters degree. However, instead of making the journey a joyride, I got in my own way and complicated things for no good reason.

 Final Thoughts

As William James said, a person can change his life by changing his attitude. All I needed to do was change my thinking -- work hard -- and the “score would have taken care of itself”.

I thought I was alone. But I found out in other spheres that a non-negligent percentage of people fall prey to the impostor syndrome. I wanted to write this to help any student who may be going through the problem that I did. If you are going through self-doubt, my message to you is to get out of the head, believe that you are capable (and make no mistake, you certainly are), do the work diligently,
follow the process, and let the score take care of itself.

Sunday, June 12, 2022

I am surprised that the Shortest Vector Problem is not known to be NP-hard, but perhaps I am wrong

A lattice L in R^n is a discrete subgroup of R^n. 

Let p IN [1,infinty)

The p-norm of a vector x=(x_1,...,x_n) IN R^n is

                                          ||x||_p=(|x_1|^p + ... + |x_n|^p)^{1/p}.

Note that p=2 yields the standard Euclidean distance.

If p=infinity  then ||x||_p=max_{1 LE  i LE n} |x_i|.

Let p IN [1,infinity]

The Shortest Vector Problem in norm p (SVP_p) is as follows:

INPUT A lattice L specified by a basis.

OUTPUT Output the shortest vector in that basis using the p-norm.

I was looking at lower bounds on approximating this problem and just assumed the original problem was NP-hard. Much to my surprise either (a) its not known, or (b) it is known and I missed in in my lit search. I am hoping that comments on this post will either verify (a) or tell me (b) with refs. 

Here is what I found:

Peter van Emde Boas in 1979  showed that SVP_infinity  is NP-hard.   
(See here for a page that has a link to the paper.  I was unable to post the link directly. Its where it says I found the original paper.) He conjectured that for all p GE 1 the problem is NP-hard. 

Miklos Ajtai in 1998 showed that SVP_2 is NP-hard under randomized reductions.  (See here)

There are other results by Subhash Khot in 2005  (see here)  and Divesh Aggarwal et al. in 2021 (see here)  (Also see the references in those two papers.)  about lower bounds on approximation using a variety of assumptions. Aggarwal's paper in unusual in that it shows hardness results for all p except p even; however, this is likely a function of the proof techniques and not of reality. Likely these problems are hard for all p.

But even after all of those great papers it seems that the  the statement:

                For all p IN [1,infinity] SVP_p is NP-hard

is a conjecture, not a theorem. I wonder if van Emde Boas would be surprised. If he reads this blog, maybe I'll find out. If you know him then ask him to comment, or comment yourself. 

SO is that still a conjecture OR have I missed something?

(Oddly enough, my own blog post here (item 5)  indicates SVP_p  is NP-hard; however, 
I have not been able to track down the reference.)

Saturday, June 04, 2022

Does the Social Media Law in Texas affect theory bloggers?

A new law in Texas states that any social media sites that has at least 50 million subscribers a month cannot ban anyone (its more nuanced than that, but that's the drift). 

(I wrote this before the Supreme courts blocked the law, which you can read about here. This is a temporary block so the issue is not settled.) 

Here is an article about the law: here

My random thoughts

1) How can any internet law be local to Texas or to any state? I wonder the same thing about the EU's law about right-to-be-forgotten and other restrictions. 

2) Does the law apply to blogs? If Scott had over 50 million readers... Hold that thought. Imagine if that many people cared about quantum computing, complexity theory,  the Busy Beaver function,  and Scott's political and social views. That would be an awesome world! However, back to the point- if he did have that many readers would he not be allowed to ban anyone?

3) If Lance and I had over 50 million readers... Hold that thought. Imagine if that many people cared about Complexity Theory, Ramsey Theory, Betty White and Bill and Lance's political and social views. Would that be an awesome world? I leave that as an open question. However, back to the point- would they be able to block posts like: 

                      Great Post. Good point about SAT. Click here for a good deal on tuxedos. 

Either the poster thinks that Lance will win a Turing award and wants him to look good for the ceremony, or its a bot. 

4) If Lipton and Regan's GLL blog had over 50 million readers.... Hold that thought. Imagine if that many people cared about Complexity theory, open-mindedness towards P=NP, catching people who cheat at chess, nice things about everyone they mention, and their political and social views. That would be a very polite world! However, back to the point- would they be able to block posts? Block people? 

5) arxiv recently rejected a paper by Doron Zeilberger. This rejection was idiotic, though Doron can argue the case better than I can, so see here for his version of events (one sign  that he can argue better than I can: he does not use any negative terms like idiot.)  Under the moronic Texas law, can arxiv ban Doron for life? (of course, the question arises, do they have at least 50 million subscribers?)

6) Given who is proposing the law its intent is things like you can't kick Donald Trump off Twitter. I  wonder if Parler or 8-chan or Truth-Social which claim to be free-speech sites, but whose origins are on the right, would block  liberals. Or block anyone? I DO NOT KNOW if they do, but I am curious. If anyone knows please post- no speculation or rumor, I only want solid information. 

7) Republicans default position is to not regulate industry. It is not necessarily  a contradiction to support a regulation; however, they would need  a strong argument why this particular case needs regulation when other issues do not. I have not seen such an argument; however, if you have one then leave a comment. (The argument they are doing it  to please their base is not what I mean- I want a fair objective argument.) 

Monday, May 30, 2022

Discussions I wish we were having

1) Democrats think the best way to avoid school shootings (and other problems with guns) is to have regulations on Guns. They have proposed legislation. The Republicans think its a mental health issue. They have proposed legislation for this. NO THEY HAVEN"T. I would respect the its a mental health issue argument if the people saying this  respected it. They do not. See here. Idea: Politico should leak a (false) memo  by Gov Abbott where he says 

We have a serious mental health crisis in Texas which caused the recent event. I am not just saying this to deflect from the gun issue. I have drawn up a bill to fund mental health care, providing more money, for care and for studies. I call on Republicans and Democrats to pass it ASAP.

I wonder- if this false memo was leaked, would he deny it and say 

I didn't write that. I am using mental health only as a way to deflect from the gun issue. How dare they say that I am reasonable and am proposing actual solutions. 

Or would he be forced to follow through?

2) Democrats think Biden won the election. Some Republicans think Trump won the election. One issue was Arizona. So some republicans organized a recount of Arizona. And when they found out that Biden really did win it they said, as the good Popperian scientists they are, we had a falsifiable hypothesis and it was shown to be false, so now we acknowledge the original hypothesis was wrong. NO THEY DIDN"T. They seem to point to the Arizona audit as proof that they were right, even though it proves the opposite. (Same for all the court cases they lost.)

3) At one time I read some books that challenged evolution (Darwin on Trial by Phillip Johnson was one of them). Some of them DID raise some good points about how science is done (I am NOT being sarcastic). Some of them DID raise some questions like the gap in the fossil record and Michael Behe's notion of irreducible complexity.  (In hindsight these were window dressing and not what they cared about.) MY thought at the time was its good to have people view a branch of science with a different viewpoint. Perhaps the scientists at the Discovery Institute will find something interesting. (The Discovery institute is a think tank and one of their interests is Int. Design.) Alas, the ID people seem to spend their time either challenging the teaching of Evolution in school OR doing really bad science. Could intelligent people who think Evolution is not correct look at it in a different way than scientists do, and do good science, or at least raise good questions,  and come up with something interesting? I used to think so. Now I am not so sure.

4) I wish the debate was what to do about global warming and not is global warming happening? Conjecture: there will come a time when environmentalists finally come around to nuclear power being part of the answer. At that point, Republicans will be against Nuclear power just because the Democrats are for it. 

5) I sometimes get email discussions like the following (I will call the emailer Mel for no good reason.)


MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your 2-coloring of K_{44} that has no mono K_5?

MEL: You are just being stubborn. Look at my proof!


Clyde has asked me what if Mel had a nonconstructive proof?

FINE- then MEL can tell me that. But Mel doesn't know math well enough to make that

kind of argument. Here is the discussion I wish we had


MEL: Dr. Gasarch, I have shown that R(5)=45.

BILL: Great! Can you email me your coloring of K_{44} that has no mono K_5?

MEL: The proof is non-constructive.

BILL: Is it a probabilistic proof? If so then often the prob is not just nonzero but close to 1. Perhaps you could write a program that does the coin flipping and finds the coloring.

MEL: The proof uses the Local Lovasz Lemma so the probe is not close to 1.

BILL: Even so, that can be coded up.



Maybe Mel really did prove R(5)=44, or maybe not, but the above conversation would lead to


Sunday, May 22, 2022

In the 1960's students protested the Vietnam war!/In 1830 students protested... Math?

 I was at SUNY Stonybrook for college 1976-1980. 

I remember one student protest about a change to the calendar that (I think) would have us go home for winter break and then come back for finals.  I don't recall how that turned out. 

However I had heard about the protests in the 1960's over the Vietnam war. Recall that there was a draft back then so college students were directly affected. 

I was reading a book `Everything you know is wrong' which noted that some people thought the first time there were student protests was in the 1960's but this is not true. (Not quite as startling as finding out that a ships captain cannot perform weddings.) 

It pointed to The 1830 Conic Section Rebellion. I quote Wikipedia (full entry is here)

Prior to the introduction of blackboards, Yale students had been allowed to consult diagrams in their textbooks when solving geometry problems pertaining to conic sections – even on exams. When the students were no longer allowed to consult the text, but were instead required to draw their own diagrams on the blackboard, they refused to take the final exam. As a result forty-three of the ninety-six students – among them, Alfred Stille, and Andrew Calhoun, the son of John C. Calhoun (Vice Pres a the time) – were summarily expelled, and Yale authorities warned neighboring universities against admitting them.

Random Thoughts

1) From my 21st century prospective I am on the students side. It seems analogous to allowing students to use calculators-- which I do allow. 

2) From my 21st century prospective the punishment seems unfair. 

3) The notion of a school telling other schools to not admit student- I do not think this would happen now, and might even be illegal (anti-trust).

4) I am assuming  the students wanted to be able to consult their text out of some principle: we want to learn concepts not busy work.  And again, from my prospective I agree that it was busy work. 

5) Since all of my thoughts are from a 21st century prospective, they may be incorrect, or at least not as transferable to the 1830 as I think. (Paradox: My ideas may not be as true as I think. But if I think that...) 

6) I try to avoid giving busy work. When I teach Decidability and Undecidability I NEVER have the students actually write a Turing Machine that does something. In other cases I also try to make sure they never have to do drudge work.  And I might not even be right in the 21st century- some of my colleagues tell me its good for the students to get their hands dirty (perhaps just a little) with real TM to get a feel for the fact that they can do anything. 

7) The only student protests I hear about nowadays are on political issues. Do you know of any student protests on issues of how they are tested or what the course requirements are, or something of that ilk? I can imagine my discrete math students marching with signs that say: 


Sunday, May 15, 2022

Is Kamala Harris our first female PREZ? No. Do I have a theorem named after me. No. But in both cases...

On Nov 19, 2021 Joe Biden got a colonoscopy and hence the 25th amendment was used to make Kamala Harris the president temporarily (this source: here says 85 minutes, though I thought I heard a few hours from other sources). 

Does this make Kamala Harris our first female president?

I would say NO and I suspect you agree. A friend of mine suggested the phrasing Kamala Harris is the first women to assume the powers of the president under the 25th amendment.  True.  I don't think it means much. She tacked on the under the 25th amendment since Edith Wilson was essentially president when Woodrow Wilson had a stroke (see here).

A student asked me Is there a theorem that is referred to as Gasarch's Theorem or something like that?

I will answer YES and NO, but really the answer is NO.

YES: In 1999 Gasarch and Kruskal had a paper in Mathematics Magazine: 

When can one load of Dice so that the sum is uniformly distributed?

In that paper we have a theorem that gives an exact condition on

(n_1,...,n_k) for when there is a loaded n_1-sided dice, n_2-sided dice,...,n_k-sided dice so that 

the sums are all equally likely.

In 2018 Ian Morrison published a paper in the American Math Monthly:

Sacks of dice with fair totals

which used our work and referred to our main theorem as The Gasarch-Kruskal Theorem.

Hence there is a theorem with my name on it!

NO: The Gasarch-Kruskal paper has only 8 citations (according to Google Scholar). This is more than I would have thought, but its not a lot. The fact that ONE person calls the main theorem THE GASARCH-KRUSKAL THEOREM hardly makes it a named theorem. 

QUESTION: So what criteria can one use?

We could say that X has a theorem with their name on it if there is a Wikipedia entry about the theorem, using that name. That works to a point, but might fun afoul of Goodhart's law (if a measure becomes a target it stops being a measure) in that, for example, I could write a Wikipedia entry on The Gasarch-Kruskal Theorem. 

We could say that 10 people need to refer to the theorem by the name of its authors. Why 10? Any number seems arbitrary. 

CAVEAT: If someone asked Clyde Kruskal is there a theorem that bears your name that is trickier, since The Kruskal Tree Theorem bears his name.... but its not his theorem. Reminds me of the (fictional) scenario where a Alice steals  a Field's medal and tells Bob I have a Field's Medal! and Bob  thinks Alice is a world-class mathematician since she has a fields medal, rather than thinking Alice is a world class thief. See here for my post on that. 

(I originally had Kruskal Three Theorem instead of Tree Theorem. I have corrected this but I hope it inspires Clyde to prove a theorem about the number Three so he can have a named theorem. And if he is lucky, over time, people will confuse it with the Kruskal Tree Theorem!) 

Tuesday, May 10, 2022

Queen Elizabeth is the 3rd longest reigning monarch; The problem with definitions

 A few days ago Queen Elizabeth passed Johann II of Liechtenstein to be the third longest reigning monarch (see here). 

A summary of the top 4:

4) Johann II, Liechtenstein ruled from Nov 12 1858 until his death on Feb 11, 1929. When he became King he was 18. He was king for 70 years, 91 days. 

3) Queen Elizabeth II (thats a two, not an eleven) ruled from Feb 2, 1952 until now. When she became Queen she was  25. I am writing this on May 10 at which time she ruled 70 years, 94 days. 

2) Bhumibol Adulyadej (Thailand) ruled from June 9, 1946 until Oct 13, 2016. When he became King he was 19. He was king for 70 years, 126 days. 

1) Louis XIV ruled from May 14, 1643 until Sept 1, 1715. When he became King he was 4 years and 8 months. He was king for 72 years, 110 days. 

Johann, Elizabeth, and Bhumibol started their reigns a bit young (they would have to to have ruled so long) but their first day of their reign they knew what the job was, what they are supposed to do etc. 

Here is my complaint: Louis XIV being king at the age of 4 years 8 months should not count (someone who proofread this post wondered if 4 years 9 months would count. No.) Shouldn't we define the reign of a king as the point at which he can make real decisions as king? Or something like that. 

For the record of the longest marriage there is a similar problem. The three longest marriages are legit in that the people got married at a reasonable age (I think all were married after they were 17). The fourth longest marriage of all time involved two people that were married when they were 5. That should not count (see here).

Is there a way to define monarch's reigns and also marriage length so that it corresponds to our intuitions? 

In Math we can use rigorous definitions but in English its harder. 

Wednesday, May 04, 2022

The (R)evolution of Steve Jobs

I don't mention it that often in this blog, but I fell in love with opera in the 90's and watch as much as I can, often fitting opera into my travels or vice-versa. Rarely do the tech world and operas collide but they did so this weekend in visit to Atlanta, I saw the (R)evolution of Steve Jobs, yes an opera about the iconic Apple founder that was first performed in Santa Fe five years ago. This production played in Austin and Kansas City earlier this year.

The story focused on relationships, Steve Wozniak, his wife Laurene, his guru Kōbun Chino Otogawa and Chrisann Brennan, the mother of Job's daughter Lisa, and on Steve Jobs focus on perfection and his company, as he often shunned others and even his own health. The music worked and the singers were generally strong. There were about 20 large monitors on the set which were used to enhance the story in pretty clever ways. The opera bounced around in time from when Steve Jobs father bought him a worktable to his memorial service. 

100 minutes is short for an opera, especially one on a person as complicated as Jobs, and some of the story lines and characters could have benefited by a longer exposition, or perhaps a more focused story could have had a larger emotional punch.

Laurene had a message at the memorial service but really meant for the audience in the opera.
And after this is over,
The very second this is over,
For better or worse,
Everyone will
Reach in their pockets,
Or purses,
And — guess what? —
Look at their phones,
Their “one device.”
I’m not sure Version 2.0 of Steve
Would want that.
Version 2.0 might say:
“Look up, look out, look around.
Look at the stars,
Look at the sky,
Take in the light,
Take another sip,
Take another bite,
Steal another kiss,
Dance another dance,
Glance at the smile
Of the person right there next to you.”
The (R)evolution of Steve Jobs has a couple of more performances in Atlanta this weekend, including a livestream, and heads to Calgary and other venues in the future.

Next year, The Life and Death(s) of Alan Turing at Chicago Opera Theater. 

Sunday, May 01, 2022

Elon Musk To Buy Complexityblog

Elon Musk has offered to buy out Complexityblog. The money is too good to turn down. As part of the contract we can't say how much or in what cryptocurrency, but suffice to say it will be more than the royalties from our books. Or not.

Readers be aware of the following changes to the blog:

1) We can no longer send Donald's Trump comments into our spam folder.

2) All of our posts will be written by Tesla autopilot.

3) Complete free speech in the comments. Or not. Depends on Elon's mood that day

4) Purchases made through this blog can be in bitcoin or other cryptocurrencies. Or not. Depends on Elon's mood that day.

5) Switch the business model (Lance- we have a business model?) from advertisements to a subscription service. How much will people pay per year to access complexity blog? 

6) Lance and I have been invited to fly to orbit on a SpaceX rocket so we can post from space. Or was it posting from the backseat of a Tesla? Depends on how you read the contract.

7)  April Fools day posts will henceforth be on May 1. 

Sunday, April 24, 2022

The Roeder Problem was Solved Before I Posed it (how we missed it)

(This is a joint post with David and Tomas Harris.)

In my an earlier post (see here) I discussed the MATH behind a problem that I worked on, with David and Tomas Harris, that we later found out had already been solved. In this post we discuss HOW this happened. 

Recall that Bill Gasarch read a column of Oliver Roeder (see here) on Nate Silvers' blog where he challenged his readers to the following:

Find the longest sequence using numbers from {1,...,100} such that every number is either a factor or multiple of the previous number. (A later column (see here ) revealed the answer to be 77 via a computer search, which we note is not a human-readable proof.)

Bill wrote a blog post (see here) and an open problems column (see here ) asking about the general case of {1,...,n}. Before doing this Bill DID try to check the literature to see what was known, but he didn't check very hard since this was not going to be a published paper. Also, he vaguely thought that if it was a known problem then one of his readers would tell him.

QUESTION: Is it appropriate to blog on things that you have not done a search of the literature on?

ANSWER: Yes, but you should SAY SO in the blog post.

As measured by comments, the post did not generate much interest- 10 comments. 2 were me (Gasarch) responding to comments.

David (who has a PhD from UMCP under Aravind Srinivasan) asked Bill to find a HS project for his son Tomas. Bill gave Tomas the sequence problem (as he called it) to look at- perhaps write a program to find what happens for {1,...,n} for small n, perhaps find human-readable proofs of weaker bound, for small n or for n=100.

David got interested in the MATH behind the problem so the project became three projects: Tomas would look at the programing aspects and the human-readable aspects, David would look at the Math, and Bill would...  hmmm, not clear what Bill would do, but he did write up a great deal of it and cleaned up some of the proofs.

David showed

Omega( n/( (log n)^{1.68} )  LE  L(n)  LE  O( n/( (log n)^{0.79} ). 

Tomas and Bill obtained a human-readable proof that L(100) LE 83. (Comments on my blog sketched a proof that L(100) LE 83, and someone else that L(100) LE 80). See my previous post (here) for more on the known numbers for L. 

At that point David did a brief literature search; however, he didn't know what to look for.

BILL still thought of this as a HS project so he didn't think much about a paper coming out of it, or if it was original. So he didn't do the due diligence of seeing what was already known.

David and Tomas were busy working on it, so they only did a few cursory checks of the literature.

With the two results above,  we had a paper! David then looked much more carefully at the literature. He DID find some earlier papers -- he did a Google search for Roeder's puzzle, which mentioned another mathematician, who was quoted in a blog by another mathematician, who eventually mentioned Pomerance's old paper on the topic. Once he found a reference to an actual math paper it was easy to use Google Scholar to find forward/backward citations and find the current state of the art.

His email had subject title

                        SHUT IT ALL DOWN!!!

Which made Bill think it involved a nuclear reactor undergoing The China Syndrome rather than just telling us that other people did had better and earlier results. 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

SO, why didn't Bill, David, Tomas find that it was already known until late in the process:

1) They didn't know the right search term: Divisor Graph

2) The literature was in French so the right search term is graphe divisoriel

3) The transition from FUN HS PROJECT to SERIOUS MATH PAPER was somewhat abrupt and caught Bill by surprise.

Was this a disappointment?

1) We all learned some math from it, so that was nice.

2) We were in a position to read and understand the paper since we knew all of the difficulties --- however, it was in French which I do not read. David reads some, Tomas does not read French.  I prefer to be scooped in English, but even then  I might not be able to read up on the problem since  math is... hard. When did math get so hard? see my blog on that here. When did CS theory get so hard? See my blog on that here.)

Could this happen again?

1) Yes. Language barriers are hard to overcome. Though this is rare nowadays--- not much serious mathematics seems to be done outside English. French mathematicians seem to like to keep their language alive, although they probably know English as well. There may be a few other countries (China, perhaps), where English language skills are not advanced and researchers are cut off from the English literature.

2) Yes. I've heard of cases where many people discovered the same theorem but were unaware of each others results since they were in different fields.

3) Is it easier or harder to reprove a theorem now then it was X years ago?

We have better search tools, but we also have more to search. 

Monday, April 18, 2022

1-week long Summer School for Ugrads Interested in Theory, and my comments on it

Recently a grad student in CS at UMCP emailed me the following email he got,  thinking (correctly) that I should forward it to interested ugrads. 


Are you interested in theoretical computer science including topics like algorithms, cryptography, machine learning, and others? If so, please consider applying to the New Horizons in Theoretical Computer Science week-long online summer school! The school will contain several mini-courses from top researchers in the field. The course is free of charge,and we welcome applications from undergraduates majoring in computer science or related fields. We particularly encourage applications from students that are members of groups that are currently under-represented in theoretical computer science.

Students from previous years have shared with us that the mini-lectures, online group activities, and interactions with other students and the friendly TAs were extraordinarily engaging and fun.

For full consideration, please complete the application (it’s short and easy!) by April 25, 2022. The summer school will take place online from June 6 to June 10.

Please see our website for details: see here 

Any questions can be directed to


A few points about this

1) I emailed them asking `why do people need to apply if its online and free?'

I had one answer in mind, but they gave me another one

Their Answer: They want to have SMALL online activities in groups. If they had X students and want groups of size g then if X is large, X/g may be too large. 

My Answer: If people REGISTER for something they are more likely to actually show up. (I know of a conference that got MORE people going once they had registation, and even MORE when they began charging for it.) 

2) I emailed them asking if the talks will, at some later point, be on line. They will be. I then realized that there are already LOTS of theory talks online that I have not gotten around to watching, and perhaps never will. Even so, the talks on line may well benefit people who goto the summer school if they want to look back and something. 

3) Online conferences PROS and CONS:

PROS: Free (or very low cost), no hassle getting airfare and hotel, and if talks are recorded then you can see them later (that applies to in-person as well). 

CONS: Less committed to going to it. Can go in a half-ass way. For example, you can go and then in the middle of a talk go do your laundry. Being FORCED to be in a ROOM with the SPEAKER may be good. Also, of course, no informal conversations in the hallways.  Also, less serendipity. 

I want to say It would to be good to see talks outside of my area however, this may only be true for easy talks, perhaps talks in a new field, OR talks that are just barely outside my area so I have some context. 

4) I was surprised I didn't get the email directly since I have more contact with ugrads (and I have this blog) then the grad student who alerted me to it. However, I have learned that information gets to people in random ways so perhaps not to surprising. 

Monday, April 11, 2022

The Roeder Seq Problems was Solved Before I Posed it (Math)

  (Joint Post by Bill Gasarch, David Harris, and Tomas Harris) 


The divisor graph D(n) is an undirected graph with

vertex set V={1,...,n}$ and

edge set E={(a,b) :  a  divides  b  or  b  divides  a }

We denote the length of the longest simple path in D(n) by L(n).

EXAMPLE: if n=10 then one long-ish sequence is


so L(10) GE 7. I leave it to the reader to do better OR to show its optimal. 


In 2017 Oliver Roeder asked for L(100) (see here) In a later post Roeder reported that Anders Kaseorg claimed L(100)=77 (see  here). Anders gave a sequence and claimed that, by a computer search, this was optimal. The column also claims that other people also claimed 77 and nobody got a sequence of length 78, so the answer probably is 77 (it is now known that it IS 77).  Roeder also mentions the case of n=1000 for which Kaseorg showed L(1000) GE 418. No nontrivial lower bounds are known. 

In 2019 I (Gasarch) asked about asymptotic results for L(n)  (see my blog post here and my open problems column here.) I began working on it with David and Tomas Harris. David proved that 

Omega( n/( (log n)^{1.68} )  LE  L(n)  LE  O( n/( (log n)^{0.79} ).

We also studied human-readable proofs that L(100) LE X for some reasonable X, though getting a human-readable proof for X=77 seemed impossible. We did get L(100) LE 83, in a human-readable proof. (Some commenters on my post to sketched a proof  that L(100) LE 83 and another that L(100) LE 80 as well.) 

 But it turned out that this problem had already been studied, predating Roeder's column. (This blog post is all about the math, bout the math, no treble.  My next post will be about how we didn't know the literature until our paper was close to being finished.) 

In 1982 Pomerance showed L(n)  LE o(n) (see here). Pollington had earlier shown 

                                          L(n) GE ne^{polylog(n)};

however, the paper is not online and hence is lost to history forever. (If you can find an online copy please email me the pointer and I will edit this post.) 

In 1995 Gerald Tenenbaum showed, in a paper written in French,  that there exists a,b such that 

                               n/(log n)^a LE L(n) LE n/(log n)^b (see here). 

More recently, in 2021, Saias showed, in a paper written in French, that 

                                      L(n) GE (0.3 - o(1)) n/log n (see here). 

(ADDED LATER:  I got a very angry email telling me that the paper was in English and that I am a moron. It turns out that the abstract is in English but the paper is in French, hence the person who send the letter only read the abstract which explains their mistake.) 

He conjectures that L(n)  SIM cn/log n where c is likely in the interval [3,7]. (Apparently, no other information is known about the relevant constant factors in the estimates.)

Interestingly, the work of Tenenbaum and Saias also demonstrates why the study of L(n)  is not an idle problem in recreational mathematics. The upper bounds come from results on certain density conditions for prime factorization of random integers. That is, given an integer x chosen uniformly at random from the range {1,..., n} with prime factorization p1 GE p2 GE ... one wants to show that, with high probability, the primes pi are close to each other in a certain sense. Most recent results on L(n) have been tied closely with improved asymptotic estimates for deep number theory problems.

Determining the value of L(100) (i.e., Roeder's problem) was mentioned in Saias's paper. He claims that L(100) = 77 was discovered by Arnaud Chadozeau, who himself has written a number of papers on other properties of D(n). Since this paper was in 2021 it was after Roeder's column; however, we believe that the different discoveries of L(100) are independent. The recent work around Roeder's column appears to be done independently from the extensive French-language literature on the topic.

The following problems are  likely still open:


a) Find L(n) exactly for as many n as you can.  This would clearly need a computer program.

A listing of L(n) for n = 1 ... 200, computed by Rob Pratt and Nathan McNew,

appears as OEIS #A337125. This also includes additional references.


b) Find human-readable proofs for upper bounds on L(n) (likely not exact) for as many

n as you can.


ADDED LATER: Gaétan Berthe emailed me 


I'm the author of the last comment on your article about Roeder Sequence , as your curious about the subject I can share what we've done with my friend Paul Revenant those last few years for fun.

It all started with a competition between our classmates (see here though note that its in French) for the 100 and 1000 cases, after a few months Paul using a MIP solver gurobi was able to found a solution of size 666, and last year by studying the structure of the 666 solution we were able, with the help of gurobi again, to prove that there was no 667 solution either.

Paul then achieve to find very probable value of the sequence for 1 to 1000 (we didn't automatize the proof of 666 but it should be doable). On my side I tried to look for good solutions for the 10000 case, again using gurobi and the structure that appeared in the solution of size 666. The structure enable to cut the problem in two subpart, so the search goes faster I was able to find a solution of size 5505.

So I would say that the two mains reasons we're able to prove optimality for high numbers as 1000 are:

- MIP solver such as gurobi are very powerful tools.

- The longest path in the divisor graph are highly structured.

I joined our informal proof of the 666 case (the solution at the end), what is interesting is to understand how the solution is composed of different blocks depending of the prime decomposition of the elements. I joined lower bound from 1 to 1000 computed by Paul, that are very likely to be optimal.


He also emailed me

1)  a list of the numbers I call L(n) for n=1 to 1000. These have not been refereed though I think they are correct. The list is here


2)  a PROOF that L(1000)\le 666 (and they HAVE a sequence of length 666, so L(1000)=666).

Again, not refereed, but you can read the proof yourself here WARNING- the proof is in ENGLISH, so you cannot use it to improve your mathematical French. 

Tuesday, April 05, 2022


Illinois Tech removed the last of their mandatory masking restrictions yesterday. Chicago had zero Covid deaths. Yet I still get messages like this in my twitter feed.

The science is unequivocal for vaccines, which do a good job preventing infection and a strong job saving lives. I just got my second booster on Sunday.

Masks give you some protection but nothing like the vaccines. It's impossible to completely remove the risk of Covid so people need to make their own choices and tradeoffs. If you are vaccinated your chance of serious illness is tiny, whether or not your wear a mask. And mask wearing is not cost-free.

I just don't like wearing masks. Wearing a mask bends my ears and is mildly painful. People can't always understand me when I talk through a mask, and they can't read my facial expressions. People and computers don't recognize me in a mask. Masks fog up my glasses. I can't exercise with a mask, it gets wet with sweat and hard to breath. You can't eat or drink wearing a mask.

Now everyone has their own tolerance and I respect that. I'll wear a mask if someone asks nicely or if it is required, like on public transit and many theaters. If I have a meeting with someone wearing a mask, I'll ask if they would like me to put mine on. In most cases they remove theirs.

On the other hand, the Chicago Symphony concert I planned to attend tonight was cancelled because the conductor, Riccardo Muti, tested positive for Covid (with minor symptoms). For my own selfish reasons, I wish he had worn a mask.

Friday, April 01, 2022

A Ramsey Theory Podcast: No Strangers at this Party

 BILL: Lance, I am going to blog about the Ramsey Theory Podcast called 

                            No strangers at this party

LANCE: Oh, so that will be your April Fools Day post? That is too unbelievable so it won't work as a joke.

BILL: Okay, you got me. But it will work if I get 14 Ramsey Theorists to do Podcasts on Ramsey Theory and pretend its coming from... where should it come from. 

LANCE: A Hungarian Middle School. 

BILL: That's  too realistic. How about Simon Fraser University in Canada?

LANCE: Why there?

BILL: Why not there?

LANCE: Knock yourself out.


At Simon Fraser University they have a podcast on Ramsey Theory. They had 14 episodes, each one was an interview with someone who is interested in Ramsey Theory. I don't like the term `Ramsey Theorist' since I doubt anyone does JUST Ramsey Theory (e.g., I do Muffins to!).

Here is the list of people they interviewed. You can find the podcasts at SpotifyAnchorApple Podcasts, and Google Podcasts.

Julian Sahasarabudhe, 

Jaroslav Nesetril

Joel Spencer 

Donald Robertson

Fan Chung

Steve Butler

Tomas Kaiser

David Conlon

Bruce Landman 

William Gasarch

Bryna Kra

Neil Hindman

Adriana Hansberg

Amanda Montejano

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. 

Saturday, February 26, 2022

I did an Instagram Live with Mohammad Hajiaghayi

 Today I did an Instagram Live with Mohammad H. He was the host, asking me questions. We discussed 

Our lives

Blogging (which I do but he does not)

Parenting (which he does but I do not)

P vs NP (which we both care about) 

Zero Knowledge and Zcash


How to inspire young minds (since I mentor many students, including Mohammad's 9 year old son)

The conversation is on you-tube here


Thursday, February 24, 2022

I will be on instagram/If you have two reals in a box- Answer (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram


This is the answer to the problem posted in the last post which was a guest post by David Marcus. This post is also a guest post by him. 

We restate the problem:



There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.


1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.


There is a strategy. In fact, we give two.


Before looking at any number, pick a number x on your own from the reals according to a distribution with full support (every open interval has prob greater than 0). Then pick a number from the box (prob 1/2-1/2), which we call y. If x<y then keep y. If y\le x then take the other number.

If x is between the two numbers, then the strategy works. If not then the strategy does not hurt, so the prob in that case is 1/2. Hence you do better than 1/2. 


Let f: R--> (0,1) be strictly increasing. Pick a number from the box, call it y. Keep it with prob f(y).

Monday, February 21, 2022

I will be on Instagram/If you have two reals in a box.... (Guest Post by David Marcus)

I will be on instragram:

We,  Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).

 We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.

#PvsNP #blogging #youngminds #instagram


 (David Marcus emailed me this for a guest post, inspired by my posts on a similar problem where I gave the question here and the answer here.)

This is a well known problem, but I have learned over time that not everyone knows things that are well known.


There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number. 

You want to pick the larger one. You can pick one of the numbers at random and look at it

before deciding which one you want. 

Is there a strategy that will win with probability > 1/2.


1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.

2) It must have prob of winning > 1/2 for EVERY pair of reals.

3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.

(Warning: I will NOT block comments that give away the answer, so if you want to work on it without knowing the answer, do not look at comments.) 

Monday, February 14, 2022

Belated happy 80th, Allan Borodin!

Guest Post by Aravind Srinivasan 

Allan Borodin turned 80 in 2021. This post is to belatedly wish him a very happy 80th, and to give a short personal perspective. 

Three things come to mind when I think of Allan:

  1. His range of research topics: I was first exposed to his work (Borodin's Gap Theorem) in a complexity-theory class by Hartmanis in Spring 1990, and have since enjoyed reading---at varying levels of depth---his works on algebraic complexity, space complexity and tradeoffs, circuit complexity, lower bounds in general, routing, adversarial queuing, online algorithms, priority algorithms, and E-commerce (I am surely leaving out some areas). This is an amazingly broad sweep!
  2. His enthusiasm in learning about and developing new models, as our field has evolved greatly over time.
  3. The enthusiastic embrace he has given to researchers spanning generations. Indeed, I am one of many who have been inspired by various facets of his research and personality.

Photos from Allan’s 60th can be seen at Amos Fiat’s page.

Thank you for everything Allan, and wishing you continued robust health and enjoyment of your academic work! 

Tuesday, February 08, 2022

A Book Break

I got the writing bug back while working on my recent CACM article and I'd like to try my hand at another book. Not sure the exact topic but something related to the changing nature of computing and its implications. 

I'll cut down my blogging for a while. I'll still post or tweet when I have something I want to say. Bill will continue to post regularly and keep this blog active.

Bill asked me if I have time to write this book as dean but he already knew the answer. Writing keeps me sane in a world that seems less and less so.

Sunday, February 06, 2022

PSPACE is contained in Zero Knowledge!! How come nobody seems to care?

(This post was inspired by Lance's post on Zero Knowledge, here, which was inspired by a video he has in the post which was inspired by... (I think this ordering is well founded.))

 ZK= Zero Knowledge.

When it was shown that NP \subseteq ZK this was a big deal. This was by Goldreich-Micali-Wigderson  (see here (FOCS-1986, JACM-1991). In the JACM paper they have the following passage:

Our result that all languages in NP have zero-knowledge proof systems, has been extended to IP, assuming the same assumptions. (The result was first proved by Impagliazzo and Yung, but since their paper [53] contains only a claim of the result, the interested reader is directed to [11] where a (different proof) appears.) In other words, whatever can be efficiently proven can be efficiently proven in a zero-knowledge manner. This may be viewed as the best result possible, since only languages having interactive proof systems can have zero-knowledge interactive proof systems.

11. BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S,,  AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology— Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.

53.IMPAGLIAZZO. R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology— Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.
Later the papers of Lund-Fortnow-Karloff-Nisan and Shamir showed IP=PSPACE. Hence

PSPACE \subseteq ZK

When I realized this I thought OH, that's interesting! I then looked around the web and could not find any mention of it. I asked Lance and some people in crypto and yeah, they all knew it was true, but nobody seemed to care.

Why the apathy? Speculation:

1) ZK is a notion people actually want to use in real crypto (and there has been some progress on that lately). The prover for ZK in PSPACE has to be way to powerful to be practical. I don't really like this explanation since we are talking about theorists. Even in crypto, which has more of a connection to the real works then, say, Ramsey Theory, there are still plenty of non-useful results. 

2) IP=PSPACE was the big news and  had interesting proof with nice ideas. Nothing crypto-ish about it. So the corollary that PSPACE \subseteq ZK is an afterthought. 

3) SAT in ZK was big news. IP in ZK is nice, but uses mostly the same ideas.

4) I am WRONG- it is a celebrated result and I somehow missed the celebration.

5) The proof that ZK is in PSPACE USES two interesting results, but adds NOTHING to the mix. In short, the proof is to easy.

Any other ideas?

Wednesday, February 02, 2022

The Beginnings of Zero-Knowledge

Wired runs this video series where topic expert explain concepts to five levels of difficulty, typically a child, teen, undergrad, grad student and expert. UCLA professor Amit Sahai took this on for zero-knowledge. 

I'd recommend the whole thing but I'd like to focus on the last segment with USC Professor Shanghua Teng (starts at 17:05). Amit nicely summed up the importance of the paper.

What was such a beautiful insight is that the idea of zero-knowledge being something that you can already predict. If you can already predict the answer, then you must not be gaining any knowledge by that interaction. This insight of being able to predict the future accurately, and that being an evidence of a lack of new knowledge.

Like Shanghua I was also assigned the seminal zero-knowledge paper by Goldwasser-Micali-Rackoff from my advisor. In many ways the original STOC paper was rough. The definitions were buggy, the examples uninspiring. Supposedly the paper didn't even get accepted into a conference in its first try. And yet as you read the paper you realize the potential, the beauty of not one but two new models that would go on to change both cryptography and complexity forever.

In the fall of 1985 when I started graduate school I took a cryptography class from Manuel Blum. Much of that class was spent on protocols that would convince you that, for example, a number was the product of three primes. By the spring of 1986, Goldreich, Micali and Wigderson distributed their paper showing, among other things, all NP problems has zero-knowledge proofs, making many of the protocols discussed in Blum's course a few months earlier trivial corollaries.

But it wasn't just zero-knowledge. Goldwasser, Micali and Rackoff (and independently Babai and Moran) developed the notion of interactive proof, a proof system with statistical confidence, a model that would lead to probabilistically checkable proofs and helping us understand the limits of approximation.

I owe most of my early research to the models developed in the GMR paper and glad that Amit has found a way to share these ideas so well.

Sunday, January 30, 2022

Regan Lipton celebrates my 1000th blog post and random thoughts this inspires

Ken Regan emailed me recently asking if our software could tell how many blogs I had done (not how many Lance+Bill had done). We didn't know how to do that but he managed it anyway. Apparently he was more interested in this question than either Lance or I was. 

But the answer was interesting: My1000th post of Complexityblog was about Betty White dying at just the wrong time to be in those those we say goodbye to articles that appear CLOSE to the end of the year. (I don't know why, but I think the fact that my 1000th post was on Betty White is just awesome!) The post is here. He was asking this because he thought (correctly) that I was around 1000 and wanted to do a tribute blog to me (actually it was done by Lipton and Regan- more on that later). And indeed they did do the post, its here.


While preparing it Ken asked me about my papers.  This brings up the more general question: When looking at your old work what do you think? Common reactions are

1) Gee, I was smarter then. That was very clever. OH, now I remember, my co-author did it. 

2) Gee, I was dumber then. I could do that argument so much better now. 

3) Why did I care about Muffins so much to write a book about it? (Replace Muffins with whatever you worked on and book with the venue it appeared in.) 

Item 3 is probably the most common: As a graduate student one works on things without really have a vision of the field (though the advisor can mitigate this) so what you work on may seem odd later on. And ones tastes can change as well. 


Ken and Dick write actual posts together. I find that amazing! By contrast, the extent of Lance and my interactions about the blog are: 

a) Someone died. Which of us should do the blog obit? or get a guest blogger.?(Whenever Lance phones me on the telephone I answer who died and usually someone did.) 

b) Which of us does the April Fools Day post this year (we usually alternate, or do we)?

c) I plan on doing 2 posts close together- a question and an answer, so when do you NOT plan on blogging so I can do that.

d) Someone proved X. Which of us should blog? Or should we get a guest blogger?

e) Establish a general rule for the year like Bill will post Sunday's, Lance Thursdays.

f) I ask Lance for technical help on the blog. How do you get rid of the white background when I cut and paste?

g) Sometimes one of us wants commentary on a blog we are working no- but that is rare. Though I asked Lance for this post and he added a few things to this list.

h) Sometimes I look at one of his posts before it goes out and offer commentary, or vice versa. Also rare.

i) Lance writes the end of year posts, but always with my input. We jointly choose the theorem of the year.

j) The very rare joint posts.

k) If we happen to be in the same place at the same time, like Dagsthul, we'll do a typecast capturing our conversations. In the past we've also had podcasts and vidcasts together.