Computational Complexity

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