Computational Complexity

1978: I took an excellent  ugrad course in combinatorics from James C Frauenthal (he sometimes wrote his name as the biniomial cofficient (J...

Illinois Tech has one of the greatest origin stories for a university. In 1890 Frank Gunsaulus, a pastor on the south side of Chicago, gave ...

 This is a Guest Post by David Marcus. He gives a puzzle and its solution, which is interesting, and then speculates as to why some people g...

First, congratulations to fellow complexity theorist and  blogger Scott Aaronson for receiving the 2020 ACM Prize in Computing for "g...

 Alice works at a charity that puts together bag and box lunches for children. They all wear masks and they are 12 feet apart and very caref...

Scott Aaronson  wrote last month about the hype over quantum computing. I'd thought I'd drop a few stories. I was once asked to rev...

BILL: Lets say we didn't know that FACTORING NPC --> NP=coNP. then what direction would we think Factoring in P or NPC?  STUDENT: In ...

This is embarrassing to admit but after a few badly timed trades on GameStop options I find myself a bit tight on money. To raise some cash,...

Here's a neat result I heard about at virtual Dagstuhl last week, a new lower bound on the number of hyperplanes that cuts all the edge...

 In my last blog post I posed a question about finding the coeff of x^100 in a particular Taylor Series. The question and answer are given  ...

 I post a problem today and its solution on Thursday. Comments are fine, though if you don't want to get a hint, don't read them.  F...

I'm absolutely elated that  Lázló Lovász and Avi Wigderson won the Abel Prize . More from the New York Times , Quanta Magazine and Gil ...

 (This post is a sequel to my post from Feb 13, 2007 which you can find  here . While the gap from 2007 until 2021 seems large, its not as l...

There's a new  proposal out of Baltimore  for a new way to handle overtime in National Football League games. This post is about America...

In a recent post  here  I mentioned in passing a plot point from the last season of The Big Bang Theory. Note that the last season was in 20...

In Thor:Ragnorak Bruce Banner mentions that he has 7 PhDs. Gee, I wonder how he managed to slip that into a conversation casually.  Later i...

The title of this post came from an opinion piece in the Wall Street Journal yesterday on vaccine distribution. Many attempts to get the va...

 In my post on Alex Trebek, see  here , I noted that Jeopardy!  is not a good name for the game show since it doesn't tell you much abou...

 Journalists sometimes get things wrong. This is not news, but it is interesting when you KNOW they are wrong.  1) Scott Aaronson has a GREA...

 If you Google Victoria Delfino you will find that she is a real estate agent in LA (well, one of the Victoria Delfino's you find is suc...