Computational Complexity

When I won't be in email contact for a while I set up a vacation program so that if someone emails me they get a message. I used to use ...

(Guest post from Shiva Kintali. All capital letters, italics, and boldface are from Shiva.) A request to FOCS/STOC PC members Hi All, I...

The game of checkers seems to have been solved. Its a draw. See here or here if you don't mind seeing an ad for low cholestrol cooking...

A PhD Student, Michal Kouril, found a new van der Waerden number, W(6.2)=1132. See here for details. I had a list of known VDW numbers in a...

The following is a quote from Comedian Jerry Seinfeld. The source is Seinfeld Universe: The Entire Domain by Greg Gattuso (Publisher of No...

I will be sending the following letter by snail mail and you should send a similar letter- you may have an effect on spam. Dear Govenor...

A blog entry of Lance's on open problems noted that it would be good to have a repository of open problems. Perhaps a wiki or something...

(Guest Post by Ken Regan) pdf file available here Computational complexity theory is the study of information flow and the effort requi...

On the post Math Terms used in Real Life- Good or Bad I mentioned the following: On 24, season two, there was a line `we can't break ...

As a collector of Novelty songs and a math-person I was morally obligated to purchase Musical Fruitcake by The Klein Four , a band consist...

Collapsing Degrees Guest post by Stuart Kurtz and Jim Royer. Bill Gasarch asked us to write an article about Collapsing Degrees, in ...

For more information on Steve Mahaney's untimely demise see here and here is how you can contribute to help honor his memory. Maha...

Guest post by Lance Fortnow I am breaking weblog silence to bring the very sad news of the loss of a co-author, good friend and great comp...

In 1985 I was 120% sure that P\ne NP. Why? Scott gave a nice list of reasons here . In 1988 I was down to 110% sure that P\ne NP. Why?...

The Computing Community Consortium (CCC- they stole our acronym!) new proposal for grants solication right here . This proposal calls for n...

Michael Mitzenmacher has a theory blog! There is a pointer to his blog from my blog page so you can use that OR just go here . The blog is c...

Scott Aaronson asks for a Complexity Theory Theme song and composed one, with help, called Down with SPP . I have not composed any, but I o...

I recently go this email from Yoav Freund PLEASE SIGN PETITION - very sad - not surprising - STOP THE ACADEMIC BOYCOTT OF ISRAEL!! On th...

Paul Beame's comment on my last blog ASK THE ALGORITHM , and one email comment that I got from someone who was hesitant to post since sh...

How do non-theorists view algorithms? If ask.com has its way they will associate algorithms with ask.com. Or they will associate ask.com wi...