Computational Complexity

Last night we had a session to remember Mikhail Alekhnovich who died earlier this month in a white-water kayaking accident in Russia. Eli B...

This week I return to Banff for Recent Advances in Computational Complexity . The mountains help attract quite an impressive collection of ...

Greg Kuperberg wrote software that runs transitive closure and other tricks on the Complexity Zoo to produce inclusion diagrams and a lis...

Is it me or does the Fields medal seem to be getting more attention this year than usual? Nothing like a famous theorem and a crazy mathemat...

Four years ago today I had my first real post announcing, among other things, that Madhu Sudan had recently won the last Nevanlinna prize. ...

Jon Kleinberg wins the Nevanlinna Prize , announced today at the 2006 International Congress of Mathematicians . Congratulations to Jon!...

The editorial board of the Elsevier journal Topology have followed the lead of the editors of the Journal of Algorithms and have resigned ...

Thanks to Claire for guest blogging during my vacation. I apologize for the various technical difficulties on the weblog last week and all s...

I was a professor at a French university from 1997 to 2002. In France, universities are legally bound to accept any student who has obtaine...

On Friday I will be flying back to the East Coast. Here is a puzzle to keep blog readers occupied while I am traveling. I write two diffe...

Why do we do research? What is our real source of gratification? I remember the answer which Andy Yao gave me many years ago. When he dis...

I have occasionally seen some comments on this blog as to how one can never know too much math. To support this statement, here is an examp...

My usual way to review conference submissions is to ask myself a few standard questions: What is the problem being studied? Is it motivated ...

Here is a puzzle from Schelling's book, Micromotives and Macrobehavior: You have a glass of gin and a glass of vermouth. You lift a tab...

Last year Ailon, Charikar and Newman designed a very simple algorithm for correlation clustering. Suppose you have a set S of n data items,...

Hi, this is Claire Kenyon and I am the guest blogger while Lance is away. I have spent the last few weeks traveling and have heard many US ...

Next week I am on vacation and off the Internet. Claire Kenyon will be your guest blogger. I get to experience the new airline rules, no wa...

The prediction market exchange Tradesports have themselves a little controversy over North Korean missiles. I have written about predictio...

Eldar Fischer reports from Haifa. Truth be told, the beginning of the missile season was a surprise for us all. It is true that enough peo...

Will we ever have useful quantum computers? Despite the "breakthroughs" we seem to have nearly every month, we are a long way off ...