Computational Complexity

Over the weekend I made an observation that gives a new (is it new?) lower bound on W(k,c). I will describe what all of this means, but ...

If you google 50 is the new 40 you get over 11,000 hits ( fifty is the new forty gets only 961 hits). What does the phrase mean? It means...

(Guest posted by request from unnamed source at NSF.) The Women in Science Award of the Maria Mitchell Association will recognize an i...

As my long time readers know, I enjoy a good Francesinha as much as the next guy, but around the time of FCRC last June I realized I was si...

Guest post by Vahan Mkrtchyan (Sequel to Graph Minor Theorem Post ) When I was a student my supervisor used to explain me that one of ...

It was one of the great mysteries of my childhood. You changed TV stations by turning a dial, a dial that started at "2". What hap...

First off, I am delighted that Lance is back! I don't think this picture of Lance looks like him. I'm looking forward to meeting Ja...

One cannot escape the tight races for the democratic and republican nominees for president. While I would never endorse any specific candida...

When I watched the Fischer-Spassky match on TV back in 1972, there was a young chess prodigy, just a few years older than me, helping with ...

The weblog has called me back. Bill and I will now jointly be posting on this blog. Many changes in my life since last March, most importa...

Guest REQUEST by Richard Beigel- NSF Guy. (I always forget formal titles.) The CDI program received around 1300 proposals. You can imag...

How many math books can you read cover-to-cover? How many have you? The problem is that while you can certainly read any discrete math (f...

Iftah Gamzu requested that I post on the following topic. When I began to do it, I realized that his email to me, edited slightly, says it a...

Today, January 10, is Donald Knuth's 70th birthday. I have some thoughts on Knuth, but I am sure that my readers have more. So, I'm...

Predictions for 2008 and beyond: In October the Democratic pundits will predict that the Democrat will win the election, and the Repub...

The past and the future use the same tune: The past: 2007, they disabled embedding so could not put it here directly. Clearly old-school...

The last comment on the last post had some questions about the graph minor theorem and (implicitly) nonconstructive algorithms in general. H...

Guest Post by Lance Fortnow We had quite an active year in complexity and Paper of the Year goes to Martin Fürer's Faster Integer Mult...

On Jan 3 is the Iowa Caucus, the first contest (or something) in the US Presidential race. The question arises: Which presidents knew the mo...

This fall in my graduate complexity courses 5/11 of the HW were group HWs. This means that The students are in groups of 3 or 4. The group...