Computational Complexity

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

The May 2007 issue of IEEE SPECTRUM has on its cover the sentence The man who loved algorithms I was thinking that it would be an articl...

Mike Pilat brought this to the attention of Lance Fortnow. Lance Fortnow brought it the attention of Bill Gasarch. Bill Gasarch brings t...

As several readers mentioned on my last post, the Godel Prize has been announced. The award goes to the authors of a PAPER and the paper ...

When I was an Undergraduate (1976-1980) the question Would you take grant money from the dept of defense? was in the air. There were...

The DEADLINE for registering for FCRC without paying a late fee is FRIDAY! However, If you want to help the organizers in terms of allo...

Frederic Green posted the following comment a while back: Have you heard any buzz from your mathematical collegues on the alleged disproof...

Coda to idiot . The posting idiot was a test case for the newly-fixed mechanism to email posts to people (some people had been getting t...

CSP stands for COMPUTER SAVY PERSON. 25 years ago the following happened: BILL: I can't get my computer to work. CSP: Just push t...

The comments on both Vijay's guest post and Lance's post brought out many comments about FOCS/STOC. People seem to have strong fee...

(Guest Post by Vijay Vazirani!) The processes of submitting FOCS/STOC abstracts and conducting PC meetings have undergone numerous change...

I recently visited my nephew and his five kids and tried to get my 8-year-old great nephew Justin interested in some math. I told him that I...

The Knuth Prize for 2007 was announced: Nancy Lynch. The formal announcement is here . The Knuth Prize is awarded for a lifetime of work in...

The website for Complexity 2007 is up now (its been up for while) CCC08 . In 2007 it is part of FCRC, a set of conference including STOC. ...

Dave Barrington suggested I blog about Paul Cohen since he just died. Scotts Blog already reported on Paul Cohen's death, and there wer...

Various people have urged Lance to keep the Blog going, perhaps under new management. Some have suggested Bill Gasarch (me) . Some have sugg...

After 4 1/2 years and 958 posts I have decided to retire from blogging. No weblog can go on forever and I would rather end on my own terms t...

Today a new Teenage Mutant Ninja Turtles movie opens. The turtles were quite popular back in the late 80's and early 90's, somehow...

So if I get a number of P=NP and P≠NP "proofs" what do the law professors get? A long email argument that most income tax is illeg...

The Federated Computing Research Conference (FCRC) has opened registration and housing . FCRC, held June 8-16 in San Diego, is a mega-conf...