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.