Computational Complexity

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...

(Guest Post by Daniel Apon.) As a follow up to the last post on Do Conferences Build Community? I offer some advice for people to get...

(Joint Post by Daniel Apon and Bill Gasarch. Does doing joint posts build community?) In GASARCH's post on Will there be a 50th CCC...

I'm heading back to Chicago this morning. Dan Spielman had a special talk in honor of his recent Nevanlinna prize. He gave an amazing ta...

Some thoughts from the  FOCS conference  in Las Vegas. One result I hadn't seen before I heard people excited by,  Determinant Sums for ...

New York Area Theory Day, Organized by: IBM/NYU/Columbia, External sponsorship by: Google, Friday, November 12, 2010 The Theory Day will...

At the 25th CCC Juris Hartmanis gave a great talk to celebrate having a 25th. Will there be a 50th? I asked people at the conference. What d...

Former blogger Michael Mitzenmacher talks about being chair and not blogging. In a day for guest posts, over at Geomblog , David Johnson wan...

Last week I had a pleasant short trip to Aarhus, Denmark for the inauguration of the new Center for Research in the Foundations of Electron...