For what d is the following true: For all 2-colorings of \(R^d\) has a mono unit square (Answering(?) the Question)

 In my last post (see here) I invited you to work on the following question:

Find a \(d\) such that

--There is a 2-coloring of \(R^d\) with no mono unit square.

--For all 2-colorings of \(R^{d+1}\) there is a mono unit square. 

Actually I should have phrased my question as What do we know about d?  

Here is what we know

a) \(d \ge 2\).  There is a 2-coloring of  \(R^2\) with no mono unit square. This is easy and I leave to you. 

b) \(d\le 5\). For all 2-colorings of \(R^6\) there is a mono unit square. I will give pointers to the relevant papers and to my slides later in this post.

c) \(d\le 4\). For all 2-colorings of \(R^5\) there is a mono unit square. This is by an observation about the proof for \(R^6\). It will be in the slides about \(R^6\).

d) \(d\le 3\). This is in a paper that the reader Dom emailed me a pointer to. Dom is better at Google Search than I am. The link is here.

MY SLIDES:

\(K_6\) is the complete graph on 6 vertices. We will be looking at 2-colorings of its edges

\(C_4\) is the cycle on 4 vertices. A mono \(C_4\) has all four edges the same color.

We need a result by Chvtal and Harary in this paper here.

Lemma: For all 2-colorings of the edges of \(K_6\) there is a mono \(C_4\).

The proof appears both in their paper,  here, and on slides I wrote here. 

Stefan Burr used this to prove the following theorem.

Thm: For all 2-colorings of \(R^6\) there is a mono unit square. 

The proof was appears (with credit given to Stefan Burr) in a paper by Erdos, Graham, Montgomery, Rothchild, Spencer, Straus, here, and on slides I wrote here.

Random Points

1) It is open what happens in \(R^3\). 

2) The proof for \(R^6\) uses very little geometry. Dom had a proof for \(R^6\) in a comment on my last post that used geometry. The proof for \(R^4\) uses geometry. 

3) An ill-defined open question: Find a proof that every 2-coloring of \(R^4\) has a mono unit square that does not use that much geometry and so I can make slides about it more easily.

For what d is the following true: for all 2-colorings of \(R^d\) there is a mono unit square (Asking the Question)

 In this post I give a question for you to think about. 

My next post will have the answer and the proof. 

1) The following are known and I have a set of slides about it here

a) For all 2-colorings of \(R^2\) there exists two points an inch apart that are the same color. (You can do this one.)

b) For all 3-colorings of \(R^2\) there exists two points an inch apart that are the same color. (You can do this one.)

c) For all 4-colorings of  \(R^2\) there exists two points an inch apart that are the same color. (You cannot do this one.) 

2) SO, lets look at other shapes

A unit square is  square with all sides of length 1.

Given a coloring of \(R^d\) a mono unit square is a unit square with all four corners the same color. 

a) There is a 2-coloring of \(R^2\) with no mono unit square. (You can do this one.)

b) What is the value of d such that 

-- There is a 2-coloring of  \(R^d\) with no mono unit square.

-- For all 2-colorings of \(R^{d+1}\) there is a mono unit square. 

My next post will tell you what is known about this problem.

Until then, you are invited to think about it and see what you can find out. Perhaps you will get a better result then what is known since you are untainted by conventional thinking. Perhaps not. 

Feel free to leave comments. However, if you don't want any hints then do not read the comments.

Favorite Theorems: Learning from Natural Proofs

October Edition

I had a tough choice for my final favorite theorem from the decade 2015-2024. Runners up include Pseudodeterministic Primes and Hardness of Partial MCSP.  But instead in memory of the recently departed Steven Rudich, this month's favorite theorem shows how to learn circuit classes that have a natural proof of hardness.

Learning Algorithms from Natural Proofs

Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets and Antonina Kolokolova

In 1993, Linial, Mansour and Nisan showed that any function f computed by a constant-depth polynomial-size AND-OR-NOT circuits (AC⁰), has a quasipolynomial-time PAC learning algorithm that, after seeing a quasipolynomial number of uniformly randomly chosen inputs x and their value f(x), can with high probability predict f on other randomly chosen inputs. Their proof works by looking a the Fourier basis of f, showing that learning the low-degree coefficients gives a good approximation to f. Their paper was one of the first to apply Fourier transformations to computational complexity. Adam Klivans did a guest post on this paper back in 2004.

Now, suppose we allow unbounded parity gates to the circuit. The Fourier argument falls apart and learning such circuits remained open for over a quarter century until the Carmosino et al. paper. Their paper uses a different technique, building on the proof of the Nisan-Wigderson pseudorandom generator function. They show that if a circuit class has a natural proof of hardness, the constructivity and largeness properties of the natural proof can break a pseudorandom generator for that class, which can then be used to create a learning algorithm. 

The authors then applied the Razborov and Rudich naturalization of Razborov and Smolensky's lower bounds for AC⁰ with parity gates to get a quasipolynomial learning algorithm for that circuit class.

Steven Rudich (1961-2024)

Complexity theorist Steven Rudich passed away on October 29 at the age of 63. His works on Natural Proofs and Program Obfuscation were both highly influential. Russell Impagliazzo had a great result with him on showing that one-way permutations alone isn't enough to get secret key-exchange.

I started graduate school in 1985 at Berkeley and Steven was the unofficial student leader of the theory group when I arrived and I got a taste of his optimistic style before I moved to MIT the following summer. I'd see Rudich at various conferences and during visits to each other's institutions. I first learned about natural proofs from a talk he gave at the University of  Chicago and we had many debates about its importance for years. Alas health issues took their toll and we lost one of the great researchers and personalities in our field.

Impagliazzo has been a friend and colleague of Steven's since they were both undergrads at Wesleyan and we asked him to write a guest post about Steven. Russell sent us a very honest and personal 7-page writeup. Too long for a blog post but I strongly recommend reading this powerful story. Also see Scott Aaronson's memories.

Higher Education Under Trump

It feels eerie as pretty much everyone seemingly avoided talking about the election. But Trump back in the White House will likely have a profound effect on US Colleges and Universities. Trump is no fan of universities and his vice-president once proclaimed "the professors are the enemy". 

While most US universities act outside of federal control, almost all of them take Federal funds in scholarships and grants and Trump could use that as a lever to push his policies.

Now Trump is always unpredictable and the courts could step in but here is what could happen.

International Students

I still remember Trump's ban on Iranians in the US and what it meant to our students and faculty at Georgia Tech. While that thankfully got blocked by the courts, who knows what will happen in this next administration.

International students at all levels in higher ed play a major role in increasing both the intellectual and financial strengths of universities. International Students, especially from some countries like China, may have a harder time coming to or staying in the US under a Trump administration or may have less desire to do so.

On the other hand last June Trump said "What I want to do and what I will do is, you graduate from a college, I think you should get automatically, as part of your diploma, a Green Card to be able to stay in this country." If that's true that will greatly increase interest among foreign students but I doubt he will carry it out.

Student Loan Forgiveness

Not going to happen

Title IX

University Title IX offices get whiplash with each change of administration. Expect Title IX (sex discrimination) protections to be watered down and eliminated for transgender individuals. 

Look at Republican States

Trump may try to apply Republican policies at state universities to all universities as a whole: Dismantling DEI efforts, weakening tenure protection, allowing campus carry of guns on campus, and "free speech" policies while limiting what can be taught and cracking down on protests.

Accreditation

Trump and republicans are no fan of accreditation, and Trump has threatened that he will replace accreditors to enforce certain points of view.

A new Mersenne Prime Has Been Found. When will we find the next one?

(Lance posted on the search for Mersenne primes in 2006 after a new one was discovered. I will comment on his post later. ADDED LATER- You Tube Video by Matt Parker on the new prime, here)

A Mersenne Prime is a prime of the form \(2^n-1\) where n is a natural number. One can show that n must be a prime. There is a list of all known Mersenne primes here. A more complete list of large primes going back to 1456 (which is not prime) when they discovered that 8191 is prime, is here.

New Mersenne primes were found in 

1985

1992 (so a 7 year gap)

1994

1996

1997

1998

1999

2001

2003

2004

2005

2005 (wow, two in one year!)

2006

2008

2008 (wow, two in one  year!)2009

2013 (so a 5 year gap)

2016

2017

2018

2024 (so a 6 year gap)

When will the next one be? Possibilities:

a) The techniques that got us to the one in 2024 are NEW and will be USED to get us some new ones soon. 

b) The techniques that got us to the one in 2024 were the old techniques on their last legs. A new idea is needed either from number theory, algorithms, or hardware. So we may not find one for a while.

I do not know which of (a) or (b) is closer to the truth. It may be hard to tell. 

There are two obstacles for making progress on numbers like this.

a) Technology, math, etc.

b) Sociology. Do enough people care about finding these numbers? 

AND these two obstacles can interact to give you either

a)  a death spiral: the problem is to hard so people don't want to work on it, and people don't want to work on it because the problem is to hard or

b) a live spiral: a breakthrough was made so lets all now really go for it!

I do not know how Mersenne primes do in this context. 

In 2006 Lance's post raised the question Why Do We Care About Finding Large Primes? 

a) We don't. Not that many people are working on this.  

b) The actual primes aren't that interesting, but the techniques used to find them might be. 

c) Why do people climb mountains?

Because they like getting frostbite!

Better off finding primes which you can do without risking life and limb. 

d) As someone who has worked on proving primes infinite using Ramsey Theory I am reluctant to tell someone else that there work is not worthwhile. I blogged on using Ramsey Theory to Proof the number of primes is infinite  here.

e) I leave the following as an open problem: Compare and contrast value and interest in finding the following:

Large Merseene Prime

Largest non-Mersenne Prime. Mersenne primes are easier to find, so most known large primes are Mersenne. Finding large non-Mersenne primes has been looked at, see here, but not much.

The Busy Beaver Function . Scott did a post on the new breakthrough here.

Small Universal Turing Machines. I did a blog post on that here. There is a cash prize for it!

Ramsey Numbers, in particular R(5). I did a blog post on the new breakthrough here.

FOCS 2024

Junior/Senior lunch in 80°F Chicago

Last summer I attended the Complexity Conference in Ann Arbor for the first time in eight years largely because it was within driving distance. So with FOCS in Chicago this year I didn't have much of an excuse to skip it. I haven't attended a FOCS in person since the 2010 conference in Vegas, though I have been at a few STOCs in that span. 

The 65th IEEE Symposium on Foundations of Computer Science is being held this week at the voco hotel, a beautiful venue in Wolf's Point where the three branches of the Chicago river meet—though you'd never know it from the windowless conference venue on the 14th floor. I'm enjoying reconnecting with colleagues old and new. Sometimes you can go back home again.

Even with triple sessions, we had 12 minute talks for most papers with longer online versions linked from the schedule page. I liked the 12-minute format; with 20 minutes, speakers tend to rush through proofs, while here, they could take their time giving high-level overviews of their papers.

Stats: 274 registrants. 157 students. 16 international. Large compared to recent years but it's not a huge conference. 133 accepted papers chosen among 463 submissions from a program committee of 47 members.

The Knuth Prize winner Rajeev Alur gave his lecture on Specification-guided Reinforcement Learning. 

The Machtey Prize for best student papers goes to Brice Huang for Capacity Threshold for the Ising Perceptron and Meghal Gupta, Mihir Singhal and Hongxun Wu for Optimal Quantile Estimation: Beyond the Comparison Model.

Best paper awards goes to Bernhard Haeupler, Richard Hladík, Václav Rozhoň, Robert Tarjan and Jakub Tětek for Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps (Quanta Article) and Mohsen Ghaffari and Christoph Grunau for Near-Optimal Deterministic Network Decomposition and Ruling Set, and Improved MIS.

Test of time Awards

• FOCS 1994: Given the three papers, Shor's quantum factoring and the Simon paper that inspired him, which I posted about recently, and Expander Codes by Mike Sipser and Dan Spielman. Dan's 1994 talk was a personal favorite, largely because he used pictures without words to effectively convey how to derive error-correcting codes from expander graphs.
• FOCS 2004: Optimal inapproximability results for Max-Cut and other 2-Variable CSPs by Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O'Donnell (one of my favorite theorems) and Worst-case to average-case reductions based on Gaussian measures by Daniele Micciancio and Oded Regev. 
• FOCS 2014: Popular conjectures imply strong lower bounds for dynamic problems by Amir Abboud and Virginia Vassilevska Williams

In 2025 FOCS goes down under to Sydney, Australia, December 15-17.

Random Thoughts on the Election

 Here are my random thoughts on the election:

1) Here is a list of things I DONT care about

 a) Candidates Gender or Race. The people who say its about time we had a female president might not want to vote for a President Marjorie Taylor Green. (A while back I thought that the first african-american president and/or first female president would be a republican since such a candidates might take some usually-democratic voters into the republican camp. One of many predictions I was wrong about.) I will note here that Kamala has rarely brought up I will be the first female prez.

b) Candidates personal lives. Attempts to tie a candidates affairs to their policies never made sense to me.

c) How well the candidate did in school. I care what they know and don't know now, and also if they know what they don't know. (Who was the last president to not have a college degree? I will tell you at the end of this post.)

d) Their religion. There were people who agreed with JFK on policy issues but did not want to vote for him because he was Catholic. I didn't understand it then nor do I understand it now. Biden is Catholic but this rarely comes up. Romney was Mormon and this only came up in the Republican primary, not in the general.  So I am glad it is no longer an issue. Having said that, we still haven't had a Jewish president, a Muslim President, or an Atheist president. 

e) Do I care if the candidate X will benefit me personally? It is very hard to tell that. Someone like Elon Musk is clearly going to support Kamala since she believes global warming is true and the e-cars will be a part of dealing with it. This is an example of someone supporting someone since it benefits them personally. Oh, bad example.

 Vance thinks people vote this way as he recently said that women past child-bearing age should not care about abortion rights.

f) There are ads that say things like I served in the military defending our country, and now I want to defined your rights to XXX. I don't see how serving in the military makes them a better senator or whatever. 

g) I don't care how they are doing at polls. Some of the articles saying that candidate X is ahead  also tend to say that that shows X  is better. I campaigned for George McGovern in 1972 and he went on to lose by a lot.  Some of my friends told me that I backed a loser and tried to make that an insult (I have better friends now). This puzzled me then since the fact that my candidate lost says NOTHING about how he would do as president.

2) DO I care about if they lie? Depends on how much and about what. That Vance changes his mind about Trump (he was anti-Trump in 2016) or that Kamala changed her mind on fracking are the standard lies that politicians always tell so I don't care about that. This may be a reflection on the low standards we have. More serious are lies that they KNOW are false and might ENDANGER people.

3) DO I care if they changed their mind on an issue. All I care about is how they feel NOW, though if they changed their mind I might not believe them.

4) I  DO care about policy and ability to get things done and to consider all sides of an issue. (I won't say what policies I like since I am trying to keep this post non-partisan).

5) Some of the attacks on Kamala have been a women should not be president. This puzzles me since there will come a time when the Republicans have a female candidate.

6) I am surprised there is anyone who is still undecided. We know both candidates  VERY WELL. What more information do you need?

7) Articles like Five Reasons Kamala Will Win or Five Reasons Trump Will Win are usually crap. For example, one of the reasons Kamala will win is People are tired of  Trump's corruption. But that just means that the author of the article is tired of it, and the author does not speak for the American people. An argument like Kamala is ahead in 5 of the 7 swing states (if it were true) is the kind of argument I want to see. More to the point- an argument that someone will win should not be partisan.

8) Since JD Vance might lose Trump some votes (actually I doubt that) I have heard the old argument that Sarah Palin cost McCain the Presidency, or at least cost him some votes. I began to think do we really know that? so I looked at some articles both new and old about this. I found things like:

The American public did not want Sarah Palin a heartbeat away from the presidency because of her views, or because of her perceived lack of intelligence or blah blah. Hence she cost McCain votes.

NONE of the articles I read pointed to polls or other EVIDENCE for this point of view.

There probably is some evidence on the issue (I do not know which way it would go)  somewhere but the LACK of any INTEREST in it bothers me.

9) I am surprised there are any undecided voters at this point. Both candidates are known to the public, so I don't see what more there is to think about. I accidentally already said this, however (a) I don't want to mess up my numbering and (ii) I do feel strongly about this point, so its worth having twice.

10) Because of Americas only-2-party-system you end up voting for people you agree with on some things but not others. I can imagine Mike Pence saying:

I prefer Trump to Kamala on the abortion issue.

I prefer Kamala to Trump on the  Hang Mike Pence issue.

Gee, who do I vote for?

 Actually he has said he is voting for neither one. 

11) IF Kamala wins then the decision to make Tim Walz her VP will be seen as genius.

      IF Kamala does not win Pennsylvania and loses the election then NOT picking Josh Shapiro (popular governor of PA) will be seen as stupid.

I call bullshit on both of those. There are SO MANY factors  at play here. This reminds me of when a basketball team wins 100-99 and the sportscasters are saying things like

The decision to concentrate on 3-point shots was genius!

12) More generally, after-the-fact pundits all have their own theories about why candidate X won, even those who were confident that candidate Y was going to win, and those theories are either partisan or just uninformed. It is hard to know what works, even after the fact.

13) I had a post, here, about breaking the record for number-of-living-ex-presidents.  I speculated that  if

a) Biden won in 2020 and lost in 2024 (I overlooked the option of his not running.)

b) Carter lives to see the winner of the 2024 election inaugurated

THEN we would have SIX living ex-presidents, which would break the record. They would be 

Carter, Clinton, Bush Jr, Obama, Trump, Biden.

If Trump wins then should Trump count? I think so- he would be a president AND an ex-president. If Kamala wins I won't have that issue. When I wrote that I didn't think Carter would last this long (he is 100), but he may very well. In fact, he has already voted!

14) Allan Lichtman is an American Historian (does that mean he studies American History or that he is American AND a historian?) who has a system to predict who will win the presidential election that has been correct 9 out of the last 10 elections. See here for his system. He predicts Kamala. I personally do not put to much stock in that since its going to be VERY CLOSE (hmmm- that's my prediction, and I could be wrong). While he is a democrat his system is OBJECTIVE-- he would have to be to be right so often. Even so, he is getting hate mail. This makes no sense. Predicting that X will happen does not mean you have an opinion about if X is good or bad. 

15) When people argue passionately about a rules change (e.g., get rid of the electoral college) I do not believe them- they would argue the other way if the current rules favored their candidate. 

16) JD Vance recently came out against the laws that say you can't wear political stuff at the polling place. He said that BOTH Kamala supporters and Trump supporters should be allowed to wear political T-shirts and hats and  what not at the polling place. NO HE DIDN"T. He applauded a Trump Supporter for calling a Poll Worker a XXX and told him to YYY in for asking her to follow the polling place's rules prohibiting political merchandise. See here. (I use XXX and YYY so that this post won't get censored as happened in the past, see here. Oddly enough, this morning the ban was lifted, so for the original post that was banned see here.)  No word yet on if he is going to praise a Texas man for punching a poll worker who told him to remove his Trump hat, see here.

17) Nikki Haley bravel tells Trump that he should not call Kamala the c-word. Actually it was not brave at all- here is here quote:

You've got affiliated PACs that are doing commercials about calling Kamala the c-word. Or you have speakers at Madison Square Garden referreing to her and her pimps. This is not the way to win women.

So being nasty to Kamala is fine in itself, but Trump shouldn't do it since it will lose him votes. 

The last president who did not have a college degree was Harry Truman.

Family Feud vs Pointless

Every now and then I feel like doing a Gasarchian post. This is one of those weeks. I'm going to look at the mathematics behind the American game show Family Feud and the British Pointless. I caught a glimpse of Pointless while I was in Oxford over the summer and then got hooked for a while on old episodes on YouTube. 

In both shows, 100 people are surveyed to give elements in a category, like "Robert Redford Films" and you get points based on how many people match the player's or team's answer. After that the similarity ends. In Family Feud you want to maximize your points, in Pointless you want to get as few as possible.

In Family Feud the categories are vague and not fact checked. If you say "The Hustler" and five other people said "The Hustler" you would get five points, even though Redford did not appear in that film. The only sanity check is that you need at least two matches to get points. The questions are often humorous or risqué like "Things people do right before going to sleep".

In Pointless if you said "The Hustler" you would get 100 points for a wrong answer. To define wrong answers, the category has to have a very formal definition: "Any movie where Robert Redford has a credited role released before 2023. TV movies and documentaries do not count. Voice-over animated films do count."

Pointless often has British-based questions. I can't name any professional darts players but apparently there are several famous ones in the UK. 

Other differences: In Family Feud, each person surveyed gives one answer. In Pointless, each person surveyed has 100 seconds to give as many answers as they can. Family Feud ends with a quick round of five categories where two players need to get 200 points total. Pointless ends where the 2-player team needs to find a pointless answer in a category.

How would AI do in these shows? I asked ChatGPT to come up with an obscure Robert Redford movie and it came up with a good one, Situation Hopeless -- But Not Serious and for a popular one Butch Cassidy and the Sundance Kid. When I asked "give me one thing people do before they go to sleep" it gave me "check their phones". AI wants us to think the last thing we should do at night is talk to AI.

Family Feud has a British version named Family Fortunes. A US version of Pointless never got past the pilot. We're not a country that likes to aim for zero. 

Contrast an Episode of Columbo with the recent Nobel Prizes

 I quote Lance's blog post (here) about Computing and the Nobels

a) On Wednesday October 9th half of the Chemistry Nobel was awarded to computer scientists Demis Hassabis and John Jumper for the protein-folding prediction algorithm AlphaFold, which I (Lance) consider the most impressive and game-changing application of machine learning.

b) The day before John Hopfield and Geoffrey Hinton were awarded the Physics Nobel for the development of neural nets that lead to AlphaFold, Large-Language models, and so much more.

Bottom line: The Nobel Prize in CHEM and PHYSICS went to COMPUTER SCIENTISTS. That's probably not quite right since I am sure that the people involved KNEW lots of Chemistry and Physics. 

In Feb 10, 1974 there was an episode of Columbo called Mind Over Mayhem (see here for a summary) where one of the plot threads was the following: 

a) Carl Finch, a great scientist, dies (of natural causes) and in his files is a ground breaking theory of molecular matter.

b) Neil Cahill who was working with Finch as a computer programmer knows about the file and codes up stuff in it and claims the work as his own.   He is initially not caught and he wins the Scientist of the Year Award. 

c) I won't get into who gets murdered or how Columbo catches them.(Has anyone in the real world been murdered because of an academic dispute?)

When I first saw it I had two thoughts:

1) If Neil had claimed co-authorship that would be more honest and hence would not need to be covered up or lead to murder. AND Neil would STILL get credit

2) More important for now: a computer programmer who coded up stuff was considered NOT part of the research in 1974. And now? Well the description of what the Nobel's did seems far more impressive than what Neil Cahill did, though since Neil Cahill is fictional it's hard to say. 

The question of  how much credit should a programmer on a project get? was unintentionally raised way back in 1974. And now? I have not seen ANY objection to computer scientists winning Nobel Prizes in Chem and Physics so the question seems to not be controversial. I agree with this though I am surprised by the lack of controversy. I also note that I used the term Programmer which is not accurate. They were computer scientists. Having said that, programmers also deserve credit. How much is hard to say. The distinction between computer scientists and programmers is also hard to say. But if programmers were considered part of the research in 1974, a fictional murder could have been prevented. 

(ADDED LATER: Lance saw this post after I posted it and emailed me a link to an article that DID hae some objections to giving a Nobel Prize for AI work. I disagree with the objections, but in the interest of being giving intelligent opposing viewpoints,   the link is here.) 

Computing and the Nobels

Herb Simon

Herbert Simon while a political scientist in the 1940s at my institution, the Illinois Institute of Technology, developed the theory of bounded rationality, realizing that people did not always make the most rational decisions because of lack of information and limited cognitive ability. After Illinois Tech, Herb Simon moved to the Carnegie Institute of Technology and in the 1960s helped found its Computer Science Department, later the Carnegie-Mellon School of Computer Science. With his colleagues at Carnegie he applied his principles to artificial intelligence with Allen Newell and J. C. Shaw leading to an ACM Turing Award in 1975. Bounded rationality would help him win the Nobel Prize in Economics in 1978.

Computing would go on to play an important role in nearly all scientific research. Most notably in 2013, biochemists Martin Karplus, Michael Levitt and Arieh Warshel won the Nobel Prize in Chemistry for their work using computers to model large molecules and simulate chemical reactions. Their entire research was done on computers, not in the lab. But no other computer scientist would win a Nobel Prize for the next 45 years. 

Demis Hassabis

That all changed last week. On Wednesday October 9th half of the Chemistry Nobel was awarded to computer scientists Demis Hassabis and John Jumper for the protein-folding prediction algorithm AlphaFold, which I consider the most impressive and game-changing application of machine learning. 

The day before John Hopfield and Geoffrey Hinton were awarded the Physics Nobel for the development of neural nets that led to AlphaFold, large-language models and so much more. Hinton with his 2018 Turing Award became only the second person, after Herb Simon, to win both prizes.

Is it physics? One podcast tried to answer this question.

Geoffrey Hinton

First of all, [Hopfield's] analogy to spin glasses is a use of a physical model. Certainly, information cannot exist in the absence of matter or energy. So ultimately, information science reduces to matter and energy as much as it reduces to mathematics. And thirdly, Nobel’s will was written in the 1890s. The first prize was awarded in 1901. Things have moved on since then. So the will prescribes physics, chemistry and physiology or medicine as the three science prizes and sometimes various Nobel committees are criticised for being a bit narrow. I think this shows. A certain creativity on the part of the academy to include a very up to date and very important field in physics by a little bit of creative accounting.

As a theorist who deals with information and computation, I disagree that these can only exist with matter and energy. The set of primes, for example, cannot fit into our finite universe.

But the third point is the most important. Nobel's will predates Turing and the development of computation as a new field. The importance of computing and artificial intelligence has take on such an importance that the Nobel Prize committees felt they needed to honor it, even if it means broadening the categories and encompassing computer science as a part of physics.

What does this mean for the Turing Award, now that computer scientists seem more eligible for Nobel prizes? I'll leave that as a open question for now.

A Trip Down Memory Lane: Desc comp, Constant Round Sorting, Division Breakthrough, Derandomization.

I  came across (by accident) the link to all of the BEATCS complexity columns from 1987 to the 2016. See HERE. (If you know a link to a more recent webpage then email me or make a comment. There is a link to all of the issues of BEATCS here; however, I want a page with just the complexity  theory columns.)

This gave me a trip down memory lane and a series of blog posts: Briefly describe an  articles and also get commentary from the original authors on what they think now about the area now.

I did the first in this series, on two articles by Eric Allender, here. Today is the second: articles by Neil Immerman, Gasarch-Golub-Kruskal, Eric Allender (again!), and Valentine Kabanets.

67) Progress in Descriptive Complexity by Neil Immerman,  1999.We usually think of P, NP, and other classes in terms of TIME or SPACE. Descriptive complexity is about defining complexity classes in terms of how they can be described in a logical language. (For reviews of three books on this topic, including Neil Immerman's, see here.) I asked Neil Immerman to comment on the state of Descriptive Complexity now and he said:

Currently the two most promising and exciting areas of progress in Descriptive Complexity are, in my opinion,

• Graph Neural Nets:  see Martin Grohe, "The Descriptive Complexity of Graph Neural Networks'', (see here);    and
  
• Graph Isomorphism: see Martin Grohe,  Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Cambridge University Press, 2017, and Anuj Dawar, "The Nature and Power of Fixed-Point Logic with Counting", ACM SIGLOG News, Jan. 2015, Vol. 2, No. 1.

 

72) A Survey of Constant Round Sorting by Bill Gasarch,  Evan Golub and Clyde Kruskal in 2000.  The model of computation is that in each round one could do lots of comparisons. Transitive closure was considered free, so the model was not practical and didn't claim to be; however, lower bounds on this model implied lower bounds on more realistic models. I asked Bill Gasarch to  comment on the paper from the perspective of 2023 and he said:

I don't think the paper is out dated in terms of later results, though the model of parallelism used is not studied anymore. A survey on sorting on more realistic models would be a good idea and may actually exist.

74) The Division Breakthrough by Eric Allender, 2001. How complicated are addition, subtraction, multiplication, and division?  The addition and subtraction algorithm that you learned in grade school is a log space algorithm (your teacher should have pointed that out to you). Multiplication is also in log space---that's an easy exercise. But what about division?  When Eric Allender was doing division in grade school he wondered can this be done in log space? This was open for quite some time, but was solved- Division is in Log Space- by Chui, Davida, Litow, in 2001 (actually done by Chui in his MS thesis in 1995 but not published until 2001. Fun Fact: Chui went to law school).  Log space is an upper bound, what about a lower bound? Hesse showed that Division is complete for DLOGTIME-uniform-TC^0.  What is needed is a complete write up of all of this in a uniform notation. Eric Allender has provided that! I asked Eric if there are more open problems in the area of complexity-of-arithmetic. He responded:

What complexity class best captures the complexity of GCD (computing the Greatest Common Divisor)?  GCD is hard for\( TC^0\) (proved in a paper I wrote with Mike Saks and Igor Shparlinski) but we have no upper bound better than P.  Similarly: What is the complexity of modular exponentiation (given x, y, and m, compute x^y mod m)?  Again, we have no upper bound better than P.  Modular exponentiation is an important subroutine in the polynomial-time algorithms for checking primality, and the lack of a better upper bound for this problem is one of the main reasons that we have no better upper bound for primality-checking than P.

...and while we're talking about the primes, let me mention that my SIGACT News article( see here) from early 2023 explains that I'm offering a $1,000 reward to anyone who can provide a modest improvement on the \(TC^0\)-hardness of primality-checking.  We currently only know a non-uniform \(AC^0\) reduction from MAJORITY to primality-checking.  I'm asking for a uniform \(AC^0\) reduction.

76) Derandomization: A Brief Survey by Valentine Kabanets, 2002. A very nice survey. Has there been progress since then? I asked Valentine and he said 

There have been new approaches to the BPP vs P question. See for example a recent survey by Chen and Tell 

New ways of studying the BPP = P conjecture (a survey)

ACM SIGACT News 2023

(available on Tell's webpage https://sites.google.com/site/roeitell/Publications)

 

Fall Jobs Post 2024

In the fall, I write a jobs post predicting the upcoming CS faculty job market and giving suggestions and links. In the spring I used to crowdsource a list of where everyone got jobs but have since outsourced the crowdsource to Grigory Yaroslavtsev. Let's start with a few announcements.

FOCS in Chicago will have a Graduating Bits on Sunday, October 27 from 12-2 PM. If you have job openings for postdocs and researchers the FOCS organizers are collecting them here, The CATCS also maintains a Theoretical Computer Science Jobs posting site. You are also free to add pointers to theory-related job listings as comments to this post. More generally in CS, there is the CRA Database of Job Candidates and the CRA and ACM job postings.

Mohammad Hajiaghayi is organizing a virtual theory jobs panel November 10th with Nicole Immorlica, Samir Khuller and yours truly. 

If you are a bit more senior, the Simons Institute is looking for a new director. 

Last year I suggested AI (which by the way just won two Nobel Prizes) wasn't dramatically affecting the CS faculty job market yet but

Many see programming, rightly or wrongly, as one of the first careers that AI will displace, which may reduce enrollment in the future, as offshoring fears drove CS enrollment down 20 years ago

It didn't take long. In two years we have gone from nearly all of our CS graduates getting jobs in the field to many of them struggling to get internships and jobs in the top companies if at all. If the past is any guide, a weak tech job market leads to fewer majors which leads to fewer slots for CS faculty. We'll start to see these trends this year and they will accelerate quickly if the tech jobs market doesn't recover.

Areas related to data such as Artificial Intelligence, Data Science and Cybersecurity, will draw the most interest. Best if you can tie your research to those areas, or at least that you are open to teaching in them.

Have a well-designed website with all your job materials and links to your papers. Make sure your Google Scholar, LinkedIn and GitHub (if relevant) sites are accurate and up to date. Make a short video describing your research to a general CS crowd. Take advantage of all the links above. Network at FOCS if you can make it. And start early. 

Emil Post Anticipated (more than anticipated) Godel and Turing

 (Thanks to James De Santis for pointing the article that inspired this post on Post. The article is pointed to in this post.)

What is Emil Post known for? I know of him for the following:

a) Post's Problem: Show that there is an r.e. set A that is strictly in between Decidable and Halt using Turing Reductions. He posed the problem in 1944. It was solved in 1956 by the priority method, simultaneously invented by Friedberg and Muchnik . (My students wondered who posted to the web first and if the other one could have seen it there.)

b) He invented Post Tag Systems, a natural problem that is undecidable. Or a model of computation. Depends on how you look at it.

c) The Kleene-Post Theorem which produces a set A that is strictly in between Decidable and Halt. It did not solve Post's Problem since A is not r.e. The proof used forcing and may have been the first or close to the first use of forcing. This was published in 1954.

In summary, I thought of Post as being a recursion theorist. 

 The more I read about Post the more I realize that calling him a recursion theorist is wrong but in an interesting way. Back in the 1950's  I am sure Emil Post was called a logician. The over-specialization that produces Recursion Theorists, Model Theorists, Set Theorists, Proof Theorist was about a decade away. In fact, people who worked in logic often also worked in other parts of math. (Post worked on Laplace Transforms. See The Post Inversion Formula as part of the Wikipedia entry on Laplace Transforms.)

I recently read the article, Emil Post and His Anticipation of Godel and Turing which shows that Post really did have some of the ideas of Godel and Turing at about the same time, and possibly before they did. I will discuss briefly what he did and why it is not better known; however, the article is worth reading for more on this.

What did Post Do? 

Part of Post's Thesis (1920) was showing that the Propositional Logic in Russell-Whitehead was consistent and complete. 

He tried to show that all of RW was consistent and complete. He got RW down to a normal form; however, he realized that rather than reducing the complexity he just localized it. In 1921 he noted the following (I quote the article).

a) Normal Systems can simulate any symbolic logic, indeed any mechanical system for proving theorems.

b) This means, however, that all such systems can be mechanically listed, and the diagonal argument  shows that the general problem of deciding whether a given theorem is produced by a given system is unsolvable.

c) It follows, in turn, that no consistent mechanical system can produce all theorems.

Wow- that sounds like the outline of a proof of Godel's Incompleteness theorem!

Why Didn't Post Publish This? 

 In 1921 Post suffered his first (of many) attacks of manic-depression. He was unable to get an academic job until 1935.  By the time he could have written a paper, his ideas were already known. Note that the items about Post I knew are all post-1940.

The Story is Interesting Because its Boring

There is no interesting conflicts between mathematicians in this story. No Newton vs Leibniz rap battle (see here) no plagiarism. Just bad timing and bad luck. So this story is not even worth  being exaggerated. 

But I find that interesting. Timing and Luck play a big role, perhaps bigger than is commonly thought.

Favorite Theorems: Gradient Descent

September Edition

Who thought the algorithm behind machine learning would have cool complexity implications?

The Complexity of Gradient Descent: CLS = PPAD ∩ PLS

John Fearnley, Paul Goldberg, Alexandros Hollender and Rahul Savani

Let's unpack these classes, subclasses of TFNP, where for every input we know there is an easily verifiable solution and we are looking at the complexity of finding it. PPAD is the class famous for having finding a Nash Equilibrium as a complete set, see this post for details.

PLS is the class of problems where we look for a local minimum. Finding a global minimum is NP-complete--think vertex cover. Finding a local minimum is often easier but still could be hard if you are optimizing over an exponential set of values.

CLS is a bit trickier to define, basically you are finding an approximate local minimum of a function mapping three real variables to one real value.

The authors show that gradient descent is complete for PPAD ∩ PLS even if you only use two input variables. Since gradient descent is in CLS, the equality follows. 

More in my 2021 post. On that post author Paul Goldberg commented

The paper is a fine example of the humorous stereotype of complexity theorists proving a problem "hard" when meanwhile the problem is being routinely solved in practice in the real world.

Nevertheless it's a neat complexity result and now officially one of my favorite theorems.

Progress on R(5). Will there be more?

 (I had a post a while back requesting people to submit open problems in Luca Trevisan's honor with deadline Oct 1. I am extending that to Oct 14, but that is a HARD deadline. See my original post which I have updated, here.)

And now back to our regularly scheduled program.

 ====================================

Breaking News: \(R(5) \le 46 \)

I know this since 46 people have emailed me this link here.

(ADDED) Recall that \(K_n\) is the complete graph on \(n\) vertices which consists of \(n\) vertices and every single pair of vertices has an edge.

Recall that R(5) is the least n such that 

For all 2-colorings of the edges of \(K_n\) there is a set of 5 vertices such that all of the edges between them are the same color.

Here is a history of what is known about R(5). It is not complete. 

Proofs of points 1 and 2 below are on my slides here.

1) Let R(a,b) be the least n such that 

For all 2-colorings of the edges of K_n there is either a RED K_a or a BLUE K_b.

Note that

R(2,b)=b

R(a,2)=a

It is well known that R(3,3)=6.

Is it well known that \( R(a,b) \le R(a,b-1) + R(a-1,b)  \).

From this one can derive \( R(5,5) = R(5) \le 70 \)

2) One can also show that if R(a,b-1) and R(a-1,b) are even then 

\( R(a,b) \le R(a-1,b) + R(a,b-1) -1 \).

From this one can derive \(R(5,5)=R(5)\le 62 \). 

3) In 1989 Exoo showed \(R(5) \ge 43 \). That is, Exoo gave a 2-coloring of \(K_{42}\) with no monochromatic \(K_5\). I was unable to find his paper online; however, there is a modern exposition of his paper here.

4) In 1997 McKay and Radzisowski showed \(R(5) \le 49\).  The paper is here. This used some clever math  and lots of computer time. This paper also has a more complete history of R(5) up to 1997 then I have in this post. (Radzisowski also has a dynamic survey of small Ramsey numbers here.)

5) In 2017 Angelveit and McKay showed \(R(5) \le 48 \). This used some clever math of  and lots of computer time. The paper is here. That is the arxiv version. The journal version is behind a paywall; however, if you want to reference it and need to know journal etc, the link is here.

6) In 2024 Angelveit and McKay showed \(R(5) \le 46 \). This used some clever math and and a big computer search. The paper is here. (ADDED LATER - they used Glucose, a SAT Solver.)

COMMENTS ON ALL THIS

1) It is widely believed that R(5)=43. 

2) I have been asked if AI or SAT Solvers will help. I asked Radziowski and Angelveit and McKay and they all thought NO. There is just no way around ALL those possiblities. 

Lance: Getting 46 via an extensive computer search using "30 years of CPU time." Hard to believe AI and SAT Solvers won't play some role in future advances. 

Bill: Some problems are just really hard for SAT Solvers. Getting \(R(5)\le 45\) may take 3000 years of CPU time. So it may not be for a while or ever. 

Bill: How about a wager? If R(5) =43 is proven by 2040 then you win, otherwise I win.

Lance: Let's make it an exact value for R(5). "Widely believed" doesn't always mean "true". What do we win?

Bill: Bragging rights! And the loser buys dinner.

(ADDED LATER- A commenter left a comment which probably means they want to ask the following:

Commenter: Since SAT Solvers did play a role in the new result, why are you skeptical that they won't play a role in getting further improvements, and perhaps finding R(5)?

Bill: Even with SAT Solvers, it is taking more and more time. Do you want in on the bet? If so then email me privately. 

)

3) IF there is some clever math that will help a lot then an AI or a Human may find it. But I am skeptical this will happen.

4) I am surprised the bound went from 48 to 46 without a paper about 47. 

5) Has any nice math come out of trying to find R(5) (and other concrete values)? 

a) YES- the work on R(k) for large k has lead to nice math.

b) NO- the results above on R(5), and the math for other concrete values has largely been clever and computer work, but nothing that generalizes that much. 

6) One of the Anonymous commenters pointed this out: here

LeetCode and AI

I often do LeetCode problems for fun. This site mainly provides short coding problems for students and others to train for the kinds of question that come up in technical job interviews. I use the site to keep up my programming skills and it often requires clever algorithms and data structures. The Daily Question is like a Wordle for recreational programmers. Try this problem which asks you to create a data structure for sets with insert, delete and get-random-element operations in expected constant amortized time.

I have to turn off GitHub Co-pilot, otherwise it will give you the solution before you even finish typing the function name. There are so many solutions to these problems out there and in the training sets for LLMs.

A student asked me last week why he should do LeetCode problems if AI can solve them all. I responded that doing the problems (and CS homework more importantly) give you the skills to understand code and algorithms and in your future jobs you'll encounter problems AI may not solve fully, or correctly, or efficiently and having those skills will allow you to solve those kinds of problems AI alone can't tackle.

But is this the right answer as AI continues to improve? Ideally we want to create students who transcend AI instead of being replaced by it. For that they need to fully understand programming and computing and be smart enough to know when and when not to outsource that skill to AI. That's the challenge for CS departments: teaching students how to use AI to make themselves better computer scientists without relying on it. It's a hard balance in a technology where we can't predict AI's capabilities at the time these students graduate.

I thought I knew what pizza was...

 On Page 75 of 

The Existential Theory of the Reals as a Complexity Class: A Compendium

by Marcus Schaefer, Jean Cardinal, Tillmann Mitzow

(see here for the paper) 

I came across the following definition:

a pizza is a mass distribution (measure) on \( [0,1]^2 \) that can be computed for polygonal subsets using arithmetic circuits.

Okay. Can I add green peppers and mushrooms?

There are many words in English that we use for math terms. How close are their English-meaning and their Math-meaning?

Greedy and Girth are pretty close.

Pizza, not so much. 

Forcing is a bit odd- when we do a forcing argument we are (say) creating a model of set theory where CH fails,  I don't think the model minds that, whereas, the term forcing in English usually means the person being forced does not like being forced.

Dynamic Programming sounds like the programmer is typing really fast.

Divide and Conquer- that matches pretty well.

Games.    There are some math papers about actual games people play. And there are also math papers that inspired Darling to say Math Games are NOT Fun Games!  I blogged about that a few times, mostly notably here.

Embracing the Future of Manufacturing

Last week I walked around the International Manufacturing Technology Show with 89,000 other participants at the McCormick Center in Chicago. I went to see how AI was affecting manufacturing and it wasn't quite the way I was expecting.

The sheer scale of physical machinery is overwhelming: from elaborate manufacturing equipment and numerous robots, to water jets performing precision cuts on metal. You also notice the international aspects--the big booths belonged to German, Japanese and Taiwanese companies, not so much American. US leads the world in many things, but manufacturing technology is not one of them.

There was one exception--the three big cloud providers: Google, Microsoft and AWS (Amazon). All, especially Microsoft, have dedicated cloud services for manufacturing. All were touting their AI services for manufacturing from predictive maintenance to Edge AI to generative AI diagnosing machine failures. It was less clear if the audience was listening.

When I walked around a Health Tech show last year, one could fee the focus on data and the excitement about AI even just a few months after ChatGPT went public. At IMTS the feeling was different. The most exciting "new technology" was allowing supervisors to get stats and adjust the machines remotely from the beach, offering retrofits to old machines to allow it to happen. One exhibitor showed me an app where a line worker could show a video to a distant supervisor to get some help (they need a new app for that?). I suggested that soon the supervisor could be replaced by AI in the app and they gave me a funny look.

The most interesting use of AI came from a small Oregon-based company Machine Research, which uses AI for small manufacturers to create bids from proposals. It's a small operations--just seven employees, basically only two developers working on the cloud. 

Like academia, the manufacturing industry is slow to change. Replacing old machines and products are expensive--you can't just do a software update. Both presidential candidates are pushing to increase manufacturing in the US but unless we can take advantage of our technical strengths, embracing the future and Industry 4.0, we'll find it hard to compete. Tariffs and financial incentives will only take us so far.

How will chatGPT affect Homework?

LANCE: I gave my final exam for my ugrad theory course (regular, Context Free, P, NP, Decidable, Undecidable) to the new ChatGPT o1 that claims to reason about math to see how it would do.

BILL: How did it do?

LANCE: Impressive--beat most of my students. Lets just say I could write a pretty good letter of recommendation.

BILL (arrogantly): I am a great problem maker, so this won't affect me. I ask problems in Grad Ramsey that ChatGPT would crash and burn on.

LANCE:  Okay big-shot, email me some HWs from Ramsey and we'll see how ChatGPT does on it.

BILL: Okay! 

[Bill emails Lance the first two HW assignments and prediction on how ChatGPT will do.

Bill predicts that it will do well on the standard problems, but crash and burn on unusual problems that (key!) are not on the web. Concepts that Bill invented just for his course. Bill is mostly correct in these predictions.]

LANCE: But how did Chatty do compared to the students who took the course?

BILL: About the same with one caveat: when ChatGPT gets something wrong its really weird- it has the look and feel of a proof but what it outputs is something no human would ever right. So it does badly on getting partial credit. And one other thing- asking it to do a proof A CERTAIN WAY or SIMILAR TO WHAT I DID IN CLASS it does badly on.

LANCE: I wonder if the same holds for Ramsey courses taught at other universities. Wait is there even any one else who teaches Ramsey theory?

BILL: Very funny. In your theory course I  assume students can't use ChatGPT on an exam so this is not really a problem. But for HW it might be a problem. It also brings up the analog of the question

do we allow students to use slide rules on an exam

LANCE: Slide rules? Your age is showing.

BILL: I am only 2 years older than you. Or is it 3? I forget these things.

LANCE: Yes, I would allow students to use ChatGPT as long as they acknowledge they did so, write up their own solution and take responsibility for any mistakes. Problem is they will just cut and past.

BILL: Lets break this down course-by-course

GRAD RAMSEY:  The students want to be there and are very good. My hope is that 

1) For standard problems they won't need ChatGPT

2) For unusual problems ChatGPT won't help. And I am good at making up unusual problems.

3) In any case, if they use it and they UNDERSTAND the answer and put it into their own words, I am okay with that.

HONORS DISCRETE MATH: Similar to Ramsey though I am a bit nervous.

UNDERGRAD THEORY  (similar to Lance's course): I would like to think its similar to Ramsey Theory.  However, I may be wrong.

ALL COURSES:

There is a more profound problem here that applies to all courses: the students may confuse getting the answer from ChatGPT with understanding. 

LANCE: ChatGPT is a hell of a lot better at solving problems than it was last week. Maybe ChatGPT won't help on the unusual problems today but that might not last for long. Perhaps the solution is to just give up on assessments and stop grading all together. Students can learn if they want to and waste their money if they don't.

BILL: That kind of change in how we educate is above my pay grade. You are a Dean, so it may be at your pay grade.

LANCE: Nope, even deans have their limits.

Natural Proofs is Not the Barrier You Think It Is

If there's a position where I differ from most other complexity theorists it's that I don't believe that natural proofs present a significant barrier to proving circuit results. I wrote about this before but I buried the lead and nobody noticed.

Let's review natural proofs. I'll give a very high-level description. Li-Yang Tan gives a good technical description or you could read the original Razborov-Rudich paper. A natural proof to prove lower bounds against a circuit class \(\cal C\) consists of a collection \(C_n\) of Boolean functions on \(n\) inputs such that

1. No polynomial-size circuit family from \(\cal C\) can compute an element of \(C_n\) for large enough \(n\). 
2. \(C_n\) is a large fraction of all the function on \(n\) inputs.
3. A large subset of \(C_n\) is constructive--given the truth-table of a function, you can determine whether it sits in the subset in time polynomial in the length of the truth-table. Note: This is a different than the usual notion of "constructive proof". 

The natural proof theorem states that if all three conditions hold than you can break pseudorandom generators and one-way functions.

My problem is with the third property, constructivity. I haven't seen good reasons why a proof should be constructive. When I saw Rudich give an early talk on the paper, he both had to change the definition of constructivity (allowing subsets instead of requiring an algorithm for \(C_n\) itself) and needed to give heavily modified proofs of old theorems to make them constructive. Nothing natural about it. Compare this to the often maligned relativization where most proofs in complexity relativize without any changes.

Even Razborov and Rudich acknowledge they don't have a good argument for constructivity.

We do not have any formal evidence for constructivity, but from experience it is plausible to say that we do not yet understand the mathematics of \(C_n\) outside exponential time (as a function of \(n\)) well enough to use them effectively in a combinatorial style proof.

Let's call a proof semi-natural if conditions (1) and (2) hold. If you have a semi-natural proof you get the following implication. 

Constructivity \(\Rightarrow\) One-way Functions Fail

In other words, you still get the lower bound, just with the caveat that if an algorithm exists for the property than an algorithm exists to break a one-way function. You still get the lower bound, but you are not breaking a one-way function, just showing that recognizing the proofs would be as hard as breaking one-way functions. An algorithm begets another algorithm. You don't have to determine constructivity either way to get the lower bound. 

Even if they aren't a great barrier to circuit lower bounds, natural proofs can be an interesting, if badly named, concept in their own right. For example the Carmosino-Impagliazzo-Kabanets-Kolokolova paper Learning Algorithms from Natural Proofs.

So if I don't believe in the barrier, why are circuit lower bounds hard? In recent years, we've seen the surprising power of neural nets which roughly correspond to the complexity class TC\(^0\), and we simply don't know how to prove lower bounds against powerful computational models. Blame our limited ability to understand computation, not a natural proof barrier that really isn't there.

Very few problems are in NP intersect coNP but not known to be in P. What to make of that?

Someone once told me:

 I was not surprised when Linear Programming was in P since it was already in \(  NP \cap  coNP  \), and problems in that intersection tend to be in P.

The same thing happened for PRIMALITY.

However FACTORING, viewed as the set 

\( \{ (n,m) \colon \hbox{there is a factor of n that is } \le m \} \),

is in \(  {\rm NP} \cap {\rm coNP} \).  Is that indicative that FACTORING is in P? I do not think so, though that's backwards-since I already don't think FACTORING is in P, I don't think being in the intersection is indicative of being in P.

Same for DISCRETE LOG, viewed as the set

\( \{ (g,b,y,p) : \hbox{p  prime, g is a gen mod p and } (\exists x\le y)[ g^x\equiv b \pmod p] \} \) 

which is in \( {\rm NP} \cap {\rm coNP} \).

1) Sets in  \({\rm NP} \cap {\rm coNP}  \) but not known to be in P:

FACTORING- thought to not be in P, though number theory can surprise you.  

DISCRETE LOG-thought to not be in P, but again number theory...

PARITY GAMES-thought to not be in P. (See Lance's post on the theorem that PARITY GAMES are in Quasi-poly time see here.) 

Darn, only three that I know of. If  you know others, then let me know.

2) Candidates for sets in \( {\rm  NP} \cap {\rm coNP} \) but not known to be in P:

Graph Isomorphism. Its in NP and its in co-AM. Under the standard derandomization assumptions GI is in AM=NP so then GI would be in \( {\rm NP} \cap {\rm coNP} \). Not known to be in P. Is it in P? I do not think there is a consensus on this. 

Darn, only one that I know of. If you know of others, then let me know, but make sure they are not in the third category below. 

3) Problems with an \( {\rm NP} \cap  {\rm coNP} \) feel to them but not known to be in P.

A binary relation B(x,y) is in TFNP if,  B(x,y)\in P and, for all x there is a y such that

|y| is bounded by a poly in |x|

B(x,y) holds.

So these problems don't really fit into the set-framework of P and NP.

TFNP has the feel of \( {\rm NP} \cap  {\rm coNP} \).

Nash Eq is in TFNP and is not known to be in P, and indeed thought to not be in P. There are other problems in here as well, and some complexity classes, and some completeness results. But these problems are not sets so not in the intersection. (I will prob have a future post on those other classes.)

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

So what to make of this? Why are so few problems in the intersection? Does the intersection = P (I do not think so)?

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

I close with another quote: 

as a former recursion theorist I hope that  \(NP \cap coNP\)=P, but as someone whose credit card numbers are on the web, I hope not. 

Favorite Theorems: Parity Games

August Edition

A quasipolynomial-time algorithm for a long standing open problem. Yes, we have two of them this decade.

Deciding Parity Games in Quasi-polynomial Time

Cristian Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan

I covered this theorem in 2017. In a parity game, Alice and Bob take turns walking along a directed graph with integer weights on the vertices and no sinks. Alice wins if the largest weight seen infinitely often is even. While it's not hard to show computing the winner sits in NP\(\cap\)co-NP and even UP\(\cap\)co-UP, the authors give the surprising result that you can determine the winner in near polynomial time.

The result has implications for modal logics, for example that model checking for the \(\mu\)-calculus can now be solved in quasipolynomial-time.

In follow-up work, Hugo Gimbert and Rasmus Ibsen-Jensen give a short proof of correctness of the parity games algorithm. Marcin Jurdziński and Ranko Lazić give an alternative algorithm that reduces the space complexity from quasipolynomial to nearly linear.

Six degrees of separation has been proven. Really?

There is a paper (see here for an article about the paper, the link to the paper itself is later) that claims to PROVE that, on average, the distance (for some definition of distance) between any two people is 6.

1) We've blogged about this kind of thing:

My Pope Number is 2

What is your Erdos Number?

The six degrees of VDW

2) The paper's link is here and in case link rot sets in, my copy of it is here.

3) The paper has 14 authors. AH- so that's why we are, on the average, 6 degrees apart- because papers have so many authors. (Actually papers in Biology  have LOTS more than 14.)

4) The paper defines a mathematical model for social networks and analyzes a persons cost and benefit of forming a connection. 

5) Is the mathematical model realistic? I think so. But its always tricky since empirical evidence already gave the answer of six. The true test of a mathematical model is to predict something we didn't already know. 

6) One thing about applying this to the real world: What is a connection? Friendship? (also hard to define), handshakes? I like the will respond to my emails metric, though that may leave out half of my colleagues and even some of my friends.

(How come people do not respond to important emails? Perhaps a topic for a later blog.) 

7) My Jeopardy number is 1 in two different ways:

a)  My co-author Erik Demaine was mentioned in a question on Jeopardy, see here and look at the 800 dollar question in Double Jeopardy, Category Boy Genius.

b) My cousin Adam Winkler's book, Gunfight,  was mentioned in a question Jeopardy, see here. It was a 400 dollar question.

In both cases the question was easy, hence my inside information did not give me an advantage. 

(Note: they were actually mentioned in an answer on Jeop since Jeop has that weird format where they give the answer and you need to find the question. For example:

Game show that has a format that Bill Gasarch thinks is stupid

What is Jeopardy?

My Quantum Summer

Rendering of PsiQuantum's facility in Chicago

I wasn't looking for quantum this summer but it found me. At various events I ran into some of the most recognized names in quantum computing: Peter Shor, Charlie Bennett, Gilles Brassard and Scott Aaronson (twice), Harry Buhrman and Ronald de Wolf.

I was invited to Amsterdam for a goodbye event for Harry Buhrman. Harry co-founded and co-led the CWI quantum center QuSoft and has now moved to London to join Quantinuum as chief scientist and I was invited to give a talk on Harry's classical complexity work before he joined the dark side. Ronald and Gilles gave talks after mine. 

On the way to Amsterdam I spent a few days visiting Rahul Santhanam in Oxford. Scott Aaronson and Dana Moshkovitz showed up with kids in tow. Scott gave a talk on AI not quantum in Oxford. I would see Scott again at the Complexity conference in Michigan.

Peter Shor and Charlie Bennett both attended the Levin Event I mentioned last week.

I talked to all of them about the future of quantum computing. Even though I'm the quantum skeptic in the crowd, we don't have that much disagreement. Everyone agreed we haven't yet achieved practical applications of quantum computing and that the power of quantum computing is often overstated, especially in what it can achieve for general search and optimization problems. There is some disagreement on when we'll get large scale quantum computers, say enough to factor large numbers. Scott and Harry would say growth will come quickly like we've seen in AI, others thought it would be more gradual. Meanwhile, machine learning continues to solve problems we were waiting for quantum machines to attack. 

My city of Chicago had a big quantum announcement, the Illinois Quantum and Microelectronics Park built on an old steel works site on the Southeast Side of the city built with federal, state and local funds as well as a big investment from PsiQuantum. I have my doubts as to whether this will lead to a practical quantum machine but no doubt having all this investment in quantum will bring more money and talent to the area, and we'll get a much better scientific and technological understanding of quantum. 

PsiQuantum's website claims they are "Building the world's first useful quantum computer". PsiQuantum is using photonic qubits, based on particles of light. Harry's company Quantinuum is using trapped ions. IBM and Google are trying superconducting qubits. Microsoft is using topological qubits and Intel with Silicon qubits (naturally). Who will succeed? They all might. None of them? Time will tell, though it might be a lot of time.

Whats worse for a company: being hacked or having technical difficulties? I would have thought being hacked but...

At the Trump-Musk interview:

1) There were technical difficulties which caused it to start late and have some other problems.

2) Musk and (I think) Trump claimed that this was a DDOS attack because people were trying to prevent Donald from having his say (listen to the beginning of the interview).

3) Experts have said it was not a DDOS attack, or any kind of attack.

(For the interview see here. If the link does not work either blame a DDOS hack or technical difficulties.)

When a company is hacked, to they admit it? This is hard to tell since if it never comes out, how do you know? 

Would a company rather admit to the public they had tech difficulties OR admit to the public they were attacked? I would think they would rather admit to the public they had tech difficulties. 

I suspect that X had tech difficulties because LOTS of people wanted to hear Trump.

Faced with this, what are Elon's options:

Options

1) Claim that this was caused because so many people wanted to hear Trump that the system could not handle it. This would make Trump look good, not make Elon look too bad, and is probably true so it won't be discovered later that he lied.

2) Claim that his system was attacked. This allows Trump to claim his enemies are out to get him, thus pushing the narrative that he is a victim. But Musk looks worse than if the system was just overloaded. Plus its false which will (and did) come out. However, there were absolutely no consequences to lying. 

I think its  unusual for a company to lie by claiming they were hacked when they weren't. If you know of any other examples then please comment.

The Levin Translation

Earlier this summer I attended a Celebration for Leonid Levin who recently turned 75. To prepare my talk I wanted to go back to Levin's 1971 two-page Russian masterpiece that covered both his independent discovery of NP-completeness and Universal Search. Boris Trakhtenbrot's wonderful Survey of Russian Approaches to Perebor has a messy translation of the Levin paper in the appendix. Could I use AI to get a cleaner version? TLDR Here's the PDF.

Let me first take a detour to when I was a graduate student in the 1980s. I went to meet my advisor Mike Sipser and found him with a couple of Russian students and postdocs carefully translating the latest paper from Alexander Razborov, then a young researcher at the Steklov Mathematical Institute in Moscow. Razborov had send a physical copy of his latest paper and they were translating word by word--would this be the paper that show NP sets don't have polynomial-size circuits and P ≠ NP? Spoiler alert: It wasn't, but the process remained etched in my memory four decades later.

But now we live in the 2020s and I turned to my friend Claude for help. I gave Claude the Russian PDF and asked Translate into English

Certainly, I'll translate the Russian text into English for you. Here's the translation:

PROBLEMS OF INFORMATION TRANSMISSION

Volume IX 1973 Issue 3

BRIEF COMMUNICATIONS

UDC 519.14

UNIVERSAL SEQUENTIAL SEARCH PROBLEMS

L. A. Levin

The article examines several well-known mass problems of the "sequential search type" and proves that these problems can only be solved in the time it takes to solve any problem of the specified type in general...

So far so good. Summarize the article.  

This article by L. A. Levin, titled "Universal Sequential Search Problems," discusses a class of computational problems known as "sequential search problems" or "enumeration problems." Here's a summary of the key points:

1. The article addresses well-known computational problems that require exhaustive search (enumeration) to solve.

2. While many classical problems have been proven to be algorithmically unsolvable, there exists a class of problems that are solvable but require an impractically large amount of computation time.

3. These problems, called "sequential search problems," include tasks like minimizing Boolean functions, searching for proofs of limited length, and determining graph isomorphism.

4. While these problems can be solved by simple algorithms that enumerate all possibilities, such algorithms require exponential time, leading mathematicians to believe that simpler algorithms are impossible.

5. The article introduces the concept of "universal sequential search problems" - problems to which all other sequential search problems can be reduced.

6. Levin presents six specific problems (numbered 1-6 in the text) and claims they are universal sequential search problems.

7. The main theorem (Theorem 1) states that if there exists any sequential search problem that cannot be solved in less than f(n) time (for some function f), then the six presented problems also cannot be solved in less than f(n) time.

8. Another important result (Theorem 2) states that for any sequential search problem, there exists an algorithm that solves it in optimal time, up to a constant factor and an additive term comparable to the input length.

9. The article suggests that this approach can be extended to most interesting sequential search problems.

10. While the article doesn't solve the fundamental question of whether these problems truly require exponential time, it establishes relationships between different problems in this class.

This work is significant in computational complexity theory, as it relates various hard problems to each other and suggests a hierarchy of difficulty among computational tasks.

The summary is almost as long as the article.

Then I noticed the term "mass problems" that occurs throughout the paper. In the translation the word "mass" seems off. What are some alternatives?

You're right to notice that the word "mass" in this context might seem unusual or potentially confusing. In the original Russian text, the term used is likely "массовые задачи" (massovye zadachi), which is a term commonly used in Russian mathematical literature. However, in English, we typically use different terminology. Here are some alternative translations that might be more appropriate in this context:

1. "General problems" or "general computational problems"

2. "Large-scale problems"

3. "Broad classes of problems"

4. "Universal problems"

5. "Widely applicable problems"

6. "Common computational problems"

7. "Algorithmic problems"

8. "Computational class problems"

9. "Generic problems"

10. "Generalized problems"

In the context of this paper, the author is likely referring to problems that are not specific to a particular instance but represent a whole class or type of problem. The term "universal" is actually used later in the paper, which aligns well with this interpretation.

So, a more idiomatic translation might replace phrases like "classical mass problems" with "classical universal problems" or "broad classes of classical problems".

This choice of wording would better convey the idea that these are problems that apply broadly across many instances or types of computational tasks, rather than being specific to a particular case.

So "mass problems" is mass as in mass audience not mass as in physics. What if we left out the word "mass" completely.

You're right, omitting the word "mass" entirely could indeed improve the clarity and flow of the translation without losing the essential meaning. Let's consider how some key sentences would read without it:

1. Instead of:

"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical mass problems was proven..."

We could have:

"After clarifying the concept of an algorithm, the algorithmic unsolvability of a number of classical problems was proven..."

2. Instead of:

"However, if we assume that there exists some (even artificially constructed) mass problem of the sequential search type that cannot be solved by simple algorithms..."

We could have:

"However, if we assume that there exists some (even artificially constructed) problem of the sequential search type that cannot be solved by simple algorithms..."

3. And for the theorem:

"If there exists any problem of sequential search (quasi-sequential search) type that cannot be solved in time less than f(n) for argument length comparable to n, then problems 1-6 also have this property."

This approach works well because:

1. The context already implies that we're dealing with broad classes of problems, not specific instances.

2. The term "sequential search problems" itself conveys the idea of a general class of problems.

3. It makes the text more concise and easier to read in English.

4. It avoids potential confusion that might arise from an unusual use of the word "mass" in this context.

So yes, simply omitting "mass" throughout the translation would likely result in a clearer, more idiomatic English text while preserving the original meaning of the article.

Give me the full translation without the mass, which Claude dutifully did. Why stick with a text version. Format this nicely in latex. 

Certainly! Here's the article formatted in LaTeX.

This LaTeX code will produce a nicely formatted version of the paper. It includes:

1. Proper title, author, and abstract
2. Sections for introduction, definitions and problems, and main results
3. Theorem, lemma, and definition environments
4. Proper mathematical formatting for equations and logical statements
5. Enumerated list for the six problems
6. Bibliography section

To compile this LaTeX document, you would need to save it as a .tex file and run it through a LaTeX compiler. The output will be a professionally formatted academic paper.

So I did and here is the final PDF. 

Russian papers at the time famously had no proofs so for fun I tried Can you fill in the proofs of the theorems

Certainly! I'll expand the LaTeX document to include proofs for the theorems and lemma. Please note that since the original paper doesn't provide detailed proofs, I'll have to construct plausible proofs based on the information given and general knowledge of the field. These proofs should be considered as educated guesses rather than the actual proofs from Levin's original work.

Here's the updated LaTeX code with added proofs.

This expanded version includes proof sketches for Theorem 1, Lemma 1, and Theorem 2. These proofs are constructed based on the information given in the paper and general principles of computational complexity theory. They should give a good idea of the reasoning behind the theorems, but may not exactly match Levin's original proofs.

The main ideas in these proofs are:

1. For Theorem 1: Using the universality of problems 1-6 to show that they must be at least as hard as any other sequential search problem.
2. For Lemma 1: Demonstrating how an arbitrary sequential search problem can be reduced to one of the listed problems (in this case, Problem 2).
3. For Theorem 2: Constructing a universal algorithm that simulates all possible algorithms in parallel, achieving optimal time complexity up to a constant factor.

These proofs maintain the paper's focus on the relationships between different types of sequential search problems and the idea of universal sequential search problems.

You can judge the proofs on your own.