Computational Complexity

Complexity Theorem of the year goes to Ryan Williams for his exciting separation of NEXP from ACC 0 . The runner up is Arora, Barak and Steu...

Yesterday the Census Bureau announced the new apportionment of the 435 representatives to states based on the 2010 census. Illinois lost on...

BREAKTHROUGH in Algorithms: Improved Algorithm for Metric TSP, (Guest Blog by Mohammad Hajiaghayi) We all recently heard about the b...

Recall the following: If A is a set then A' (pronounced 'A jump') is the halting set relative to A. Formally it is: { e | M...

In the last month we have reported on NEW RESULTS by Williams , Katz and Guth , Sanders , and Pinkerton and Setra . For a change of pace let...

(CONGRADS to all the new ACM fellows . Among them are theorists Jennifer Chayes, Anne Condon, Phil Klein, S. Muthu, and Dan Spielman.) ...

From Ryan Willams' paper : Non-uniform lower bounds establish impossibility results for computation in the physical world: it could b...

We use the following terminology: [n] means the set {1,...,n}. k-AP means an arithmetic progression of length k. A 3-free set is one with n...

What advantages can we get from computational hardness? Cryptography and pseudo-random number generators come to mind. But perhaps the unive...

Last week I attended the Army Research Office sponsored  Workshop on Reasoning in Adversarial and Noncooperative Environments  related to To...

(All papers referred to in this post can be accessed from my website on the Erdos Distance Problem. ). In 1946 Erdos raised the followin...

I don't do tweets-I don't think I have enough interesting 140-char notes to tell people (though that doesn't stop Lance). Howeve...

Last week, the complexity theory bloggers  Dick ,  Scott ,  Luca  and myself  all heaped praise on Ryan Williams' new circuit lower boun...

(There are TWO theory day events in NY this semsester: Nov 11, 2010 and Nov 12, 2010 . The first one has likely already started as you rea...

Fellow blogger Scott Aaronson  was chosen as one of 19 NSF PECASE awardees and wins a trip to the White House. Congrats to Scott! He receiv...

On October 8th, when in my graduate complexity course as we discussed the 1987 Razborov-Smolensky result that one can't compute the Mod ...

You can now watch videos of the recent FOCS talks online . Glencora, who I had the pleasure of meeting at the conference, has her favorites ...

As a grad student (1980's) I found a book in the library that claimed to solve Fermat's Last Theorem using elementary methods. (This...

(There are TWO theory day events in NY this semester: Thu Nov 11 . and Fri Nov 12 .) BILL: Will you be going to the RALLY TO RESTORE SAN...

In 1973 Donald Knuth searched for a name for the hardest problems in NP. Steve Cook didn't give a name in his paper and Karp called them...