Computational Complexity

The National Science Foundation is one of the agencies most affected by the various executive orders issued by the Trump administration. As ...

In writing the drunken theorem post , I realized I never wrote a post on Lautemann's amazing proof  that BPP is contained in \(\Sigma^p_...

 44*44=1936. 45*45=2025. This year! 46*46= 2116. Since my fake birthday is Oct 1, 1960 (I do not reveal my real birthday to try to prevent I...

What does an 1838 painting tell us about technological change? A colleague and I decided to see how well LLMs could teach us a topic we knew...

I made up a quiz about the American Presidents  here .   It has 40 questions. In the modern electronic age you can probably look up most or ...

Slide in Lev Reyzin 's JMM talk "Problems in AI and ML for Mathematicians" Reyzin is paraphrasing Telgarsky. Posted with permi...

Guest Post from Nick Sovich.  ----------------------------------------------------------------------------- Bill Gasarch recently blogged on...

 BILL: Good news for Jimmy Carter! He won  The Betty White Award! (see here ). LANCE: That's not good news. He had to die to get it. BIL...

In Jan of 2023 I estabalished the Betty White Award, see  here  which is given to people who died late in the prior year and hence won't...

Bill's SIGACT Open Problems Column  remembering Luca Trevisan is out. I chose the problem of whether Promise-ZPP in P implies Promise-BP...

Back in the day (circa 1989) we studied locally random reductions which would lead to all those exciting interactive proof results. Somehow...

I've heard a few times recently the phrase "Information only exists in a physical state". It come from the quantum computing w...

 (I wrote this post without any AI help. OH- maybe not- I used spellcheck. Does that count? Lance claims he proofread it and found some typo...

We use grades to evaluate students and motivate them to learn. That works as long as grades remain a reasonably good measure of how well the...

In Lance's last post (see here ) he listed his favorite theorems from 1965 to 2024. There are roughly 60 Theorems. I mostly agree with h...

Now in one place all of my sixty favorite theorems from the six decades of computational complexity (1965-2024). 2015-2024 Graph Isomorphism...

 (I got this material from a nice article by Arthur Benjamin here .)  Conway suggested the following trick to determine if a number is divis...

Will our writing all converge to a generic AI style?  Let's take a quick detour into LaTeX. Back in the late '80s, before LaTeX was ...

 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 ...

 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 ...