Computational Complexity

There's a scene in Apollo 13 where Jim Lovell, played by Tom Hanks, asks Houston control to check his calculations, which they do using...

In the past, new PhD students would ask how they could succeed when they had to compete with the likes of say, Richard Karp or Avi Wigderson...

Lance has posted about his, and around 160 others, being laid off from IIT  here .(IIT stands for Illinois Institute of Technology which is ...

Enjoying Idaho while ignoring Illinois Today is the first day of my life that I am unemployed. And not by choice. As I mentioned on LinkedIn...

(Some of this came from a Reddit post  I read, and some of  the comments on it.)  Here are theorems with names that I think are funny or unu...

I was watching a Jeopardy from 2004 (The Game Show Channel is rerunning Ken Jennings streak) and the following question raises a good questi...

Let's say there is a statement in math T that you wonder whether it's true or false.  You may even make a conjecture of which way it...

Back in the 90s when I was a young professor at the University of Chicago, we would have a Complexity Class of the Week  where I would take ...

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterje...

Herman Chernoff passed away on July 6, 5 days after turning 103. Ravi Boppana wrote a guest post about Chernoff's life for his 100th b...

The excellent graphic novel Prime Suspects: The Anatomy of Integers and Permutations by Andrew Granville and Jennifer Granville,  illustrate...

Two editorials in the July issue of the Communications of the Association for Computing Machinery ask about the decay and future of the org...

I recently read Alan Alda's first memoir  Never have your dog stuffed   which was pretty good. Hence I began looking for more informatio...

Harry Lewis pointed Bill and me to Gottfried Leibniz's 1677 treatise  The True Method  (translated from the original French ). I highly ...

Peter Brass is a prior NSF theory director. He has written an intelligent guest post on the new NSF guidelines that we present here. You...

When you start thinking deeply about a mathematics problem you may enter the "zone", a period of intense focus where you think sol...

(All references in this blog post can be found in the main article the post is about which is  here .) Recall that \(R(s,k)  \) is the least...

Last week I saw a talk by Northwestern professor Nina Wieda on the history of the Silk Road , a network of trading routes across Asia active...

A mnemonic device is a sentence where the first letters of the words are helpful to remember something. My favorite one is                 ...

There are two ways to look at the P v NP problem, as a formal mathematically defined conjecture as a Clay Millennium Prize Problem, and as t...