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.