Computational Complexity

Thanks to Technorati I can track who links to this weblog. Recently an Indian student Nitish Korula started a new blog Pseudo-Random Thou...

A New York Times essay looks at the hardness of understanding math. The essay quotes from the book The Millenium Problems by Keith Devli...

Many universities try to integrate information technology into many different disciplines usually through their computer science departmen...

Some strong comments on Rocco's post on the recent Columbia theory day. In my own highly biased point of view, I find the study ...

A question from a reader (slightly edited): There are no part-time (or even full time) Ph.D. programs at top universities in computer s...

A report from Theory Day co-organizer Rocco Servedio On Friday May 14 a special Columbia/IBM Research/NYU Theory Day was held at Col...

On Friday I went to an alumni reception for Jeffrey Lehman , new president of Cornell University. Besides learning that the cinderblock d...

April Edition No single topic has dominated computational complexity over the past dozen years than probabilistically checkable proofs (PCP...

For those with an interest in auction theory, the Google IPO auction gives an interesting testbed for auction mechanism design. Instead of ...

The Journal of the ACM has started asking for page charges. Author's institutions or corporations are requested to honor a page ...

A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references ...

I'm moving my web hosting service--if you can read this you are accessing the new host. I will wait a day or two to post again until the...

Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership r...

[A report from weblog correspondent Bill Gasarch. Link to Allender's talk added 5/7] On Wednesday April 28 there was a SYMPOSIUM ...

A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gödel Prize . I wish this was an ...

The Unofficial Guide to Walt Disney World 2004 gives a lesson on complexity by describing the optimal tour of the Magic Kingdom as a trav...

From the PODC (distributed computing) mailing list via Harry Buhrman. Usually the winners are kept secret until the ICALP or STOC conferenc...

From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH ) from the Washington CSE Band . The best on...

Alan Kay will receive the 2004 Turing award . It can't always be a theorist. Registration is open for the 2004 Conference on Computat...

Help me solve this problem, write the paper with me, get an Erdös number of 3 and it won't cost you a cent . We can have #P functions h...