Computational Complexity

Richard Lipton has a relatively new weblog . Quite a few provocative posts, particularly on the following  theme . Hopefully, these post...

I have received the following legit email several times (paraphrased): `Hi, I am NAME (A NAME I DO recognize from my past). Are you the s...

The Guardian has an article about the beauty of algorithms which credits mathematicians as the developer of algorithms (as opposed to comp...

The 2009 FOCS Call for Papers has a few changes from previous calls. "Optimization" is added to the list of topics. The 2009 Ca...

Consider the following: Canonical VDW thm: For any k &isin N, for any coloring of N with an infinite number of colors, either there...

[Dan Spielman has posted the call for papers for the 50th(!) FOCS conference. Submission deadline is April 2. The conference itself runs O...

Note the following two movies mistakes. Or are they mistakes? In The Wizard of Oz when the Scarecrow gets his diploma (instead of a brai...

Timothy Gowers has suggested a line of research about the Density version of the Hales-Jewitt Theorem. . What is remarkable about what he p...

The Sloan Foundation took out a full page ad in the New York Times today to announce the new Sloan Fellows . Many from our community on that...

Suppose you had no specific reason to be on campus. No classes, no talks, no scheduled meetings with students/advisors, no meetings schedule...

Last reminder: Complexity submission deadline tonight midnight Eastern. In a nice move, Mitzenmacher posted both the titles and abstracts...

(This article had help from Clyde Kruskal, Joe Kruskal, Bill Kahn, Hans Courant, and Lucy Moser.) Bill James, the baseball statistician, ...

Many articles of interest in the New York Times. Chris Maase pointed me to the article Scientists Disappointed by Direction of Financing . ...

Jason Hartline comments on a report by CNN about the size of the government bailout. "To put a trillion dollars in context, if you ...

Josh Burdick had my course on concrete complexity a long time ago. He still dabbles in the area and recently sent me two manuscripts here ...

Alice: Does Carol's proof solve your big open problem? Bob: Yes, but it's an ugly proof so it doesn't count. A beautiful pro...

There is a new BLOG on our blogroll. It is Blown to Bits and it is associated to the book Blown to Bits: Your Life, Liberty, and Happiness ...

The stimulus package being shopped to congress by the Obama administration includes a considerable amount of science funding. The House pass...

Just got back from vacationing in Obama's other home state and found a new govenor in Illinois when I got back. About time. TTI-Chicago...

The James Bond Movie Goldeneye had the following scene which is typical of movies and some TV shows. Scenario: A (good) female Russian c...