Complexity in Michigan

Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets,
2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasan
and 2025 Local Arrangements chair Swastik Kopparty enjoy some tapas.

I have a long history with the Computational Complexity conference. I attended the first 26 meetings (1996-2011) and 30 of the first 31. I chaired the conference committee from 2000-2006. According to DBLP I still have the most papers appearing in the conference (32). I even donated the domain name for the conference (with the caveat that I could keep the subdomain for this blog).

Only Eric Allender had a longer streak having attended the first 37 conferences through 2022 in Philadelphia (if you count the two online during the pandemic) before he retired.

But I haven't been back to Complexity since that 31st conference in Tokyo in 2016. Due to my administrative roles, various conflicts and changes in the field you just start missing conferences. But with the conference at the University of Michigan in Ann Arbor within driving distance of Chicago it was time to go home for the 39th meeting. And it's a good thing I drove as more than one person had flight delays due to the Crowdstrike bug.

The complexity conference remains relatively stable at about 75-100 registrants, the majority students and young researchers. I've moved from wise-old sage to who is that guy. But I'm having great fun talking to old acquaintances and new. I'm impressed with the newer generations of complexity theorists--the field is in good hands.

Best paper goes to Michael Forbes Low-Depth Algebraic Circuit Lower Bounds over Any Field. the work of Limaye, Srinivasan and Tavenas I talked about last month gave an explicit polynomials with superpolynomial-size over constant depth algebraic circuits but it required polynomials over large fields. Forbes extended the lower bounds to all field sizes.

Best student paper goes to Ted Pyne from MIT for Derandomizing Logspace with a Small Shared Hard Drive for showing how to reduce space for randomized log-space algorithms on catalytic machines.

Check out all the papers in the online proceedings.

From a relatively quiet business meeting: 36 papers accepted out of 104 submissions, a bit up from previous years. 75 attendees including 42 students, similar to recent years. 2025 conference at the Fields Institute in Toronto August 5-8. 2026 in Lisbon or Auckland.

The loss of Luca Trevisan, PC Chair 2005 and local arrangements chair in 2013 in San Jose, loomed large in the business meeting and at the conference.

FLT solution annouement had its 31's anniv was about a month ago. Some poems about FLT NOT from ChatGPT

On June 21, 1993, at the Issac Newton Institute for Mathematical Science, Andrew Wiles announced that he had proven Fermat's Last Theorem. That wasn't quite right- there was a hole in the proof that was later patched up with the help of Richard Taylor (his former grad student). A correct proof was submitted in 1994 and appeared in 1995. Wiles is the sole author. 

June 21, 2024 was the  31st anniversary of the announcement. (So today is the 31-years and 1-month anniversary).  I COULD have had ChatGPT write some poems about it. But there is no need. There are already some very nice poems about it written by humans. Will humans eventually lose the ability to write such things? Would that be a bad thing? Either ponder those questions or just enjoy the poems. (My spellcheck still thinks ChatGPT is not a word. It needs to get with the times.)

1) A link to a set of poems about FLT: here.

2) Here is a poem that is not in that set but is excellent.

A challenge for many long ages
Had baffled the savants and sages
Yet at last came the light
Seems that Fermat was right
To the margins add 200 pages 

(I don't know who wrote this or even where I read it. If you know anything about where it was published or who wrote it, please let me know.)

3)  Here is a poem by Jonathan Harvey that mentions the gap in the original proof.

A mathematician named Wiles
Had papers stacked in large piles
Since he saw a clue
He could show Fermat true
Mixing many mathematical styles

He labored in search of the light
To find the crucial insight
Young Andrew, it seems
Had childhood dreams
To prove Mr. Fermat was right

He studied for seven long years
Expending much blood, sweat, and tears
After showing the proof
A skeptic said “Poof!
There’s a hole here”, raising deep fears.

This shattered Mr. Wiles’s belief
His ship was wrecked on a reef
Then a quick switcheroo
Came out of the blue
Providing his mind much relief.

Mr. Wiles had been under the gun
But the obstacle blocking Proof One
Fixed a much older way
From an earlier day
And now Wiles has his place in the sun

4) Here is a poem by John Fitzgerald that mentions other unsolved problems including P vs NP

Fermat’s theorem has been solved,
What will now make math evolve?

There are many problems still,
None of which can cause that thrill.

Years and years of history,
Gave romance to Fermat-spree,

Amateurs and top men too,
Tried to push this theorem through.

Some have thought they reached the goal,
But were shipwrecked on the shoal,

So the quest grew stronger still;
Who would pay for Fermat’s bill?

So what is now the pearl to probe,
The snark to hunt, the pot of gold,

The fish to catch, the rainbows end,
The distant call towards which to tend?

One such goal’s the number brick,
where integers to all lengths stick:

To sides, diagonals, everyone,
Does it exist or are there none?

Then there are those famous pearls,
That have stymied kins and earls:

Goldbach, Twin Primes, Riemann Zeta;
No solutions, plenty data.

Find a perfect number odd;
Through 3n + 1 go plod;

Will the P = N P ?
Send a code unbreakably.

Are independence proofs amiss;
Continuum Hypothesis;

Find a proof which has some texture
of the Poincaré conjecture.

And so, you see, onward we sail,
there still are mountains we must scale;

But now there’s something gone from math,
At Fermat’s end we weep and laugh.

The Story of Shor's Algorithm

The quantum factoring algorithm of Peter Shor (FOCS 1994, SIAM Review 1999) turns thirty this year. Before his algorithm, quantum computing lacked the killer app, something practical that quantum could do that seems hard for classical computers. Back in 1994, I said Shor's algorithm bought quantum computing another twenty years. How I misjudged the longevity of quantum hype. 

Peter got the idea for his algorithm from a paper by Daniel Simon solving a theoretical complexity problem. The quantum factoring algorithm is a great example of how a complexity result can open doors to new algorithmic ideas.

Simon came up with a beautifully simple example of a problem that required exponential-time on a probabilistic machine but polynomial-time on a quantum computer. Let's define addition over the \(n\)-bit strings, for \(x\) and \(y\) in \(\{0,1\}^n\), \(x+y\) is the bitwise parity of \(x\) and \(y\). For example if \(x\) is 0110 and \(y\) is 1100, \(x+y = 1010\).

Suppose we have a Boolean function \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) (maps \(n\) bits to \(n\) bits) with the property that \(f(x)=f(y)\) iff \(x=y+z\) for some fixed \(z\). The problem is given \(f\) as an oracle or a circuit, find the \(z\). A classical machine would need exponential steps in to find \(z\) in the worst case.

Simon gave a simple quantum algorithm that would with a single query output a random w such that \(w\cdot z=0\). With \(n = \log N\) linearly independent \(w\), you can solve for \(z\).

Shor's asked what if we could do the same for regular integer addition instead of bitwise parity. Suppose you have a function \(f(x)=f(y)\) iff \(x-y\) is a multiple of \(z\) for a fixed \(z\). (In Simon's case over bits the only multiples are zero and one.) That means \(f\) is periodic and \(z\) is the period. Shor knew that by an algorithm by Miller, finding a period leads to factoring.

Let m be an odd number with multiple prime factors. Consider \(f(x)=a^x\bmod m\) for a randomly chosen \(a\) relatively prime to \(m\). If this function has a period \(z\), then \(a^z\bmod m=a\), \(a^{z-1}\bmod m=1\) and with probability at least one-half, the gcd of \(a^{\frac{z-1}{2}}\) and \(m\) will be a nontrivial factor of m. 

Getting all this to work on a quantum computer requires a number of addition tricks beyond what Simon did but once Shor had the inspiration the rest followed. 

Peter Shor really understood the landscape of theory from complexity to cryptography, a curiosity for quantum computing and the vision to see how it all connected together to get the quantum algorithm that almost single-handedly brought billions of dollars to the field. 

Peter just received the Shannon Award for his work on quantum error correction that would help enable quantum computers to run his algorithm. Still the largest number present day quantum computers can factor with the algorithm is 21. If (and its a big if) that number gets up past the RSA challenge numbers, Peter will have far larger prizes in his future.

The Term Quantum Being Misused ... Again

In a post from 2015 I noted that the word quantum is often misused (see here). Have things gotten better since then? I think you know the answer. But two uses of the word quantum caught my attention

1) The episode Subspace Rhapsody of  Star Trek- Strange New Worlds is described on IMDB as follows:

An accident with an experimental quantum probability field causes everyone on the Enterprise to break uncontrollably into song, but the real danger is that the field is expanding and beginning to impact other ships--- allies and enemies alike.

 (I mentioned this episode and pointed to my website of all the songs in it  here.)

SO- is this an incorrect use of of the word quantum? Since ST-SNW is fictional, its a silly question. However, it seems like a lazy Sci-Fi convention to just use the word quantum for random technobabble. 

2) The Economist is a serious British weekly newspaper. Or so I thought until I read this passage in the June 15-21, 2024 issue, the article featured on the cover The rise of Chinese Science

Thanks to Chinese agronomists, farmers everywhere could reap more bountiful harvests. Its perovskite-based solar panels will work  just as well  in Gabon as in the Gobi desert. But a more innovative China may also thrive in fields with military uses, such as quantum computing or hypersonic weapons.

So The Economist is saying that Quantum Computing has military uses. I am skeptical of this except for the (in my opinion unlikely) possibility that QC can factor and break RSA which, if it will happen, won't be for a while. 

It also makes me wonder if the rest of the paragraph, which is on fields I don't know anything about, is also incorrect or deeply flawed. (See Gell-Man Amnesia which I've also heard called The Gell-Man Affect.) 

I am not surprised that ST:SNW uses quantum incorrectly (Or did it?  Maybe an experimental quantum probability field would cause people to sing.) but I am surprised that The Economist  misused it. I thought they were more reliable. Oh well. 

 

Favorite Theorems: Extracting Ramsey Graphs

June Edition

Two decades ago, I named the recently departed Luca Trevisan's paper connecting extractors to psuedorandom generators as one of my favorite theorems from 1995-2004. I'm dedicating this month's favorite theorem to him.

Suppose we have two independent sources with just a little bit of entropy each. Can I pull out a single random bit? This month's favorite theorem shows us how, with a nice application to constructing Ramsey graphs.

Explicit Two-Source Extractors and Resilient Functions

Eshan Chattopadhyay and David Zuckerman

More formally (feel free to skip this part) suppose we had two independent distributions U and V each of poly log min-entropy, which means for every string x of length n, the probability of choosing x from U and the probability of choosing x from V is at most \(2^{-(\log n)^c}\) for some c. There is a deterministic polytime function (which doesn't depend on U and V) such that f(x,y) with x and y chosen independently from U and V will output 1 with probability \(1/2\pm\epsilon\) for \(\epsilon\) smaller than any polynomial.

Previous work required a linear amount of min-entropy for U and V. 

As a corollary, we can use f to deterministically generate a Ramsey graph on n vertices with no cliques or independent sets of size \(2^{(\log\log n)^c}\) for a sufficiently large c. This is also an exponential improvement from previous constructions. Gil Cohen gave an independent construction that doesn't go through extractors.

There have been several papers improving the bounds of Chattopadhyay and Zuckerman. In FOCS 2023 Xin Li gave a construction of extractors with \(O(\log n)\) min-entropy, the current state-of-the-art for extracting a single random bit with constant error, and Ramsey graphs with no cliques or independent sets of size \(\log^c n\) for some constant c.

The combinatorics of picking a Vice President

 Trump is pondering who to pick for his vice president. For a recent podcast about it go here. Spoiler alert: Doug B or Marco R or J.D. Vance. 

In 2008 I did a blog post titled  I would bet on INTRADE that INTRADE will do badly picking VP nominations where I showed that about half the time the VP candidate is not on anyone's short list, and hence would do badly in betting markets. At the time INTRADE was synonymous with betting markets. I would  not have bet that INTRADE would go out of business. 

What criteria does a prez nominee  use when picking a vice president? How many combinations are there? 

1) Someone who will help with a block of voters. 

Trump-Pence 2016: Mike Pence was thought to help Trump with Evangelicals and establishment Republicans.

Biden-Harris-2020: Kamala Harris was thought to help Biden with women and African-Americans.

JFK-LBJ-1960-LBJ was thought to help JFK in the South. 

Kerry-Edwards-2004: Edwards was thought to help win  North Carolina (Edwards state). It didn't work. 

Dukakis-Bentson-1988- Mike Dukakis (liberal) picked Lloyd Benson (moderate) as the VP. The ticket lost though its possible that Benson brought in some votes, just not enough.

There are other examples. Even for the cases where the candidate won its not clear if the VP mattered.  The podcast says that Trump thinks that this kind of thing (e.g., picking a women or an African American) won't help him get their votes. He might be right. But (my speculation) a women on the ticket might help some men be more comfortable voting for him. That is, they could think Trump is not a misogynist, see- he picked a women for VP.  Similar for an African-American.

Caveat: Perhaps a candidate who would help in Swing States.

2) Someone who will help him if he wins. 

Obama-Biden-2008:  Biden helped new-comer Obama since Biden had Congressional experience, having been a senator for X years for some large value of X.

Bush-Cheney-2000:  Dick Cheney knew Washington DC and hence could help George W Bush (who had been a governor but had no FEDERAL experience).

3) Someone who the voters can see taking over the presidency in case that is needed.

Clinton-Gore-1992: I've heard that Clinton chose Gore for that reason. I'm NOT an insider so it may not be true. 

FDR-Truman-1944: The party chose Harry Truman as VP knowing that FDR would likely pass away and we'd have President Truman. (I've read this and believe it is true on some level.) 

4) Party Unity- Pick someone who you fought in the primary to show that the party is united. Bonus: the VP nominee has been vetted and is some-known to the public. 

Biden-Harris-2020 may have had had some of this.

This mentality is rarer now since people tend to NOT pick people they ran against in the primary lately.

JFK-LBJ-1960 was in this category.  

Biden did run for the nomination in 2008 but didn't run much (I think he dropped out either right before or right after the Iowa Caucus) so that one doesn't really count.

5) DO NO HARM. Counterexamples:

Some people voted against McCain since they didn't wan to see Sarah Palin one heartbeat away from the presidency. This was especially important since McCain was old. And hence this may be important for Trump in 2024.

Biden may have the same problem with  Harris. Note that the issue is NOT if Harris would BE a bad prez, its if people THINK she would be a bad Prez.

Krisiti Noem- Trump doesn't want to answer questions about why his VP shot a dog and a goat. (Note- if Trump himself had shot a dog and a goat the party and FOX news would be defending that action.) 

6) Someone who the Prez candidate gets along with personally. I've heard that Clinton-Gore and Obama-Biden got along. JFK and LBJ did not.

7) Someone who won't outshine the president.

Dukakis-Benson=1988  might have had this problem. 

 8) All of the above might matter less than usual since there are so few undecided people in swing states. And that's NOT just because the country is polarized. Ponder the following:

In most elections its either two people NEITHER of whom has been president, so you don't quite know what they will do, OR one has been prez and the other has not, so you don't know what the newcomer will do.

But in this election BOTH have been president. We KNOW what they will do. So there is less room for doubt. 

History: This only happened once before: 

1884: Cleveland beats Blaine

1888: Harrison beats Cleveland

1892: Cleveland vs Harrison and Cleveland wins

Even though I say its hard to predict, and it could be someone NOT on the short list, here are my thoughts.

a) Marco R. The electors in the electoral college cannot vote for a Prez and vice-Prez who are residents of the same state. (Note1- This is an idiotic rule which dates from either the late 1700's or the early 1800's. Note2- Dick Cheney changes his residency from Texas to Wyoming so he could be Bush's VP in 2000.  I have NO problem with that whatsoever.) So one of Marco R or Trump would have to change residencies. Trump won't bother. Marco R is a SENATOR from Florida so I doubt he would either. Also, Marco said nasty things about Trump when he ran against him for the nomination in 2016. I am surprised Marco is on anyone's short list. NOT going to be VP nominee.

b) Doug B. Who? He doesn't outshine Trump, and he gets along with Trump. Won't bring in any voters, but Trump says he doesn't care about that. How would American's view him as a possible prez? I doubt Trump cares. QUITE POSSIBLE to be VP nominee.

c) JD Vance. Author of a thoughtful book, Hillbilly Elegy, which indirectly explains why poor white rural voters are attracted to Trump. He then became a Senator and is now all-in on Trump. This is NOT hypocritical, but its odd. In 2016 he was anti-Trump but now he is pro-Trump. Even that is NOT hypocritical using the usual standards for politicians. He has praised Trump and there may be people who think he would be a good president. He is young (39) and handsome, so I wonder if Trump worries that Vance might outshine him. Even so QUITE POSSIBLE to be VP nominee.

d) I am surprised that Tim Scott and Elise Stefanik seem to have fallen out of Trump's Short list, though they were at one time on it, so would not be to big a surprise if either becomes the VP nominee.  IF one thinks that Tim Scott will help with the African-American vote, or that Elise Stefanik will help with the women-vote (OR as noted above, would help white men feel more comfortable voting for Trump) then either would be a politically good choice. However, Trump does not think this is true, and he may be right.  I've also heard that Trump doesn't want people saying something like Tim Scott helped Trump win the African-American Vote since Trump wants to think that HE won the election without help. I would think neither will be VP but YOU NEVER KNOW.

e) Someone NOT on the horizon. This brings us back to my 2008 post- IT REALLY COULD BE SOMEONE THAT NOBODY IS TALKING ABOUT. So Who? I DON"T KNOW SINCE NOBODY IS TALKING ABOUT THEM. Maybe Lance.

Why is called the Turing Award (revisited)?

Avi Wigderson gave his ACM Turing Award lecture last week, and instead of telling his own story, he focused on Alan Turing and his influence on complexity. If you didn't see it live, you can watch on YouTube or below.

I want to revisit a post I wrote for the Turing centenary in 2012 asking why the prize is named after Turing. Since that post, Turing has become even more popular, especially through the 2014 movie starring Benedict Cumberbatch. I caught this picture of Turing as a legend in the Chicago Pride Parade last Sunday.

But Turing was not always a legend. The first Turing award was awarded to Alan Perlis in 1966. Turing's work during World War II remained classified until the 1970s and wasn't widely known until the 80's. Alan Turing's homosexuality would have granted him no favors in the mid-60s. 

When I gave a talk celebrating Juris Hartmanis, I posited that Juris not only received the Turing award but may have been the reason the award has its name. The Hartmanis-Stearns paper, as Avi also noted, established the Turing machine as the right model for studying computational complexity, as the model easily capture time and space (memory). That paper was published in 1965, fresh in the minds of those at the ACM creating the award. Perhaps combined with the early days of AI and Turing's intelligence paper, may have been enough to decide to name the award for Turing. 

Today there is no question that ACM made the right move in naming the award for Turing. Just watch Avi show that Turing's influence on complexity justifies the award's name on its own.

Technology: 1966, 2006, 2023.

 In 2013 I wrote a blog to celebrate Lance's 50th birthday by contrasting what things were like when Lance was 10 to when he was 50. That post is here.

But life has even changed from 2006 to 2023. I will tell three stories, one from 1966, one from 2006, one from 2023. They all have to do with my hobby of collection novelty songs; however, I am sure there are similar stories in other realms

1) On Sept 21, 1966 there was an episode of Batman with special guest villain The Minstrel. He sang several songs in the episode that I thought were funny. My favorite was when Batman and Robin are tied up over a rotisserie, the Minstrel sings, to the tune of Rock-a-bye baby. 

Batman and Robin Rotate and Resolve

As the heat grows, your bodies Dissolve

When its still hotter, then you will Melt

Nothing left but your Utility Belt. 

I LIKED the song and WANTED it. So I found out when the episode would re-run and set up my tape recorder to record it. I still have the tape, though I don't have a tape player (see my blog post here) however it doesn't matter because a compilation of the songs in  that episode (actually two episodes) is on YouTube here.

2) On March 6, 2006 there was an Episode of Monk Mr. Monk goes to the dentist which has in it The Randy Disher Project singing Don't need a badge. This was great and I wanted that song. At the time I was buying the DVDs of Monk. When the DVD of that season came out I assumed the song  would be included as an extra. It was not :-(.  By that time I was busier than in 1966 so I  didn't have the time, patience, or tape recorder to track it down. But that does not matter since 8 years later it was on  YouTube here. But I had to wait 8 years.

3) On Aug 23, 2023 there was an episode of ST-SNW entitled Subspace Rhapsody that had NINE songs in it, sung by the crew (actually sung by the actors!)  I don't have streaming so I didn't watch it but I heard about it (people know I am interested in novelty songs so they tell me about stuff like that). I spend about 30 minutes on YouTube finding ALL NINE and putting them in my file of novelty song links, see here. And it was worth the effort- three of the songs are GREAT and the rest are pretty good (in my opinion).

Points

1) Also easier to find now then it was in 2006 and certainly in 1966: Everything. Okay, lets list some examples: Music (not just novelty), TV shows, Movies, Journal articles, Conference articles, books. But see next point. 

2) Big Caveat: For a recording from 1890 to have survived it would have to be on wax cylinder, then vinyl, then CD, maybe back to vinyl (Vinyl is having a comeback), and perhaps mp3, streaming, You Tube, or Spotify. Some music will be lost. I would like to think that the lost music is not the good stuff, but I know of cases that is incorrect (my blog post here gives an example). For journal articles there is also the issue of language. Some articles were never translated.  And some are written in a style we no longer understand. And some you really can't find. And there may be some songs where the only copy is in my collection.

3) Corollary to the Big Caveat: Some things are on YouTube one day and gone the next. There is an SNL short video Conspiracy Theory Rock which seems to come and go and come and go. I don't think its on YouTube, but I found it here. Lets hope it stays. I have that one on VHS tape but I don't have a VHS tape player. And modern e-journals might vanish. See my post on that issue here.

4) Some of my fellow collectors think they miss the days when only they had access to (say) Weird Al's Patterns which he sang on Square One Television (a math-for-kids show on PBS which I discovered and liked when I was 45). The song is on YouTube here. I find this point of view idiotic. The PRO of the modern world is I can find lots of stuff I like and listen to it (and its free!). The CON is a loss of bragging rights for people like me. Really? Seems like a very minor CON. I do not miss the days of hunting in used record shops for an old Alan Sherman record (ask your grandmother what a used record shop is and what an Alan Sherman is).

5) When I played the song Combinatorics (see here) in my discrete math class the students liked it (for some reason the TA hated it, oh well) and the students asked 

Is that a real song

I asked them to clarify the question. They couldn't. To ask if it ever came out on a physical medium is a silly question- it didn't, but that doesn't matter. Did it make money? Unlikely, but that would be a rather crass criteria. There are lots of VERY GOOD songs on You Tube (whether Combinatorics is one of them is a question I leave to the reader) so the question Is that a Real Song is either ill-defined or crass. All that matters is do you like it.