Computational Complexity

We go all the way back to January for the paper of the year, Mark Braverman's  Poly-logarithmic independence fools AC0 circuits . Runner...

(This is my last blog of the year. Lance will interrupt his blog sabbatical to do an END OF THE YEAR blog later.) The TV show MONK rece...

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to constru...

The following problem was problem 1 (the easy one) on the Maryland Math Competition 2009 (I will later report on how the students did on it...

(Tal Rabin requested to post this so I am doing so. This post is essentially her email, so call it a guest post.) There will be a Women ...

(Deadline to submit a paper to CCC is Dec 15. Depending on when you read this that could be today or in the past.) As you all know fro...

Submissions to 25th CCC are due TOMORROW! (Actually it could be TOMORROW, TODAY, or IN THE PAST depending on when you read this.) Should yo...

With the end of the fall quarter I will take a break from the blog for a few months. This is not another End , just a chance to move my crea...

BILL : Clyde is teaching a graduate course titled Games, Game Theory, and the Theory of Games . He tells me that there are basically eight k...

(The 17x17 problem has gotten far wider attention than I imagined--- Brian Hayes posted it on his website: here , and its also here and her...

After a talk on derandomization at Midwest Theory Day, someone asked if those techniques could also be used in quantum computing.  In cla...

Quick announcement: If you are a student who wants to go to SODA but doesn't have the funds, click here . I had forgotten we did this. ...

Dean Foster asked me for a probability that P=NP. Now P=NP is not a probabilistic event, either P=NP or P≠NP (if it's independent it...

Congrats to ALL of the ACM Fellows which were annouced here . There are several theorists among them. I could try to list them or count ...

One of the comments on my last post, the 17x17 post, inquired if I am also interested in the other unknown grids (NOW just 17x18, 18x18,21x1...

If Professor Alice at Faber College visits Dr. Bob at the University of Southern North Dakota, who should cover Alice's expenses?  It de...

The 17x17 challenge: worth $289.00. I am not kidding. Definition: The n x m grid is c-colorable if there is a way to c-color the vertic...

First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US. Here's an interesting approac...

Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event. DIMACS  has served the theoretical computer science comm...

As most of you know there are 7 problems worth $1,000,000 (see here ). It may be just 6 since Poincare's conjecture has probably been s...