Computational Complexity

Last Sunday the New York Times ran a front-page article Scientists Worry Machines May Outsmart Man  that read a bit like a bad science ficti...

A type of advertisement I think is very odd is the following: Be the first on your block to have NAME OF PRODUCT ! It might be more hon...

A great new result in quantum complexity, Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous have shown that QIP is contained in P...

On the blog we have a straightforward post policy, Bill and I try to make one post on nearly every work day. Occasionally we'll have ext...

To find out about papers that might spark my interest and lead to the following: Papers. I saw Moser's paper in STOC 2009 and I alre...

The August CACM has my viewpoint article Time for Computer Science to Grow Up  about the urgent need for conference reform. Our conference s...

The book  Patent Failure by James Bessen and Michael J. Meurer notes that considerable more money is spent on litigation defense for techno...

I received a tiny raise for the next academic year but at least it is positive. Many of my academic colleagues have salary freezes or small ...

One of the main topics of discussion at CCC last week centered around the problems with the Electronic Colloquium on Computational Complexit...

It is my first memory of a major event. Forty years ago today, my brother and a not-quite six-year old me were in my grandmother's apart...

I twittered  about some interesting papers, the business meeting and various other impressions. Since I don't have much time to write...

Live from the 24th CCC conference in Paris, Bill, Lance and special guests talk about our firsts in our first vidcast . I apologize for the ...

I arrived at the Institut Henri Poincaré in time to catch the last half of Ryan Williams giving a talk on our paper with Rahul Santhanam. I...

Tonight I fly off to Paris for the 24th IEEE Conference on Computational Complexity , the namesake conference of the blog. If the plane arri...

Ryan O'Donnell, reporting from last week's ICALP in Rhodes. ICALP has a pretty large number of papers, divided into three tracks....

I thought about doing a post on ADVICE FOR GOING TO CCC 2009, but I recalled that my advice from a 2007 blog posting will suffice. . CONG...

The 12th  TARK and 10th  EC conferences both are being held at Stanford this week, both look at questions relating economics and computer ...

Speedup for Natural Problems (Guest post by Hunter Monroe.) Blum proved speedup for an artificially constructed problem; this paper (arXi...

This week I'm at Stanford for the TARK and EC conferences co-located for the first time. Next week in Paris for Complexity . Also a sh...

Farrah Fawcett and Michael Jackson died the same day (June 25, 2009). Who is the most famous pair of people that died the same day? Whi...