Computational Complexity

The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities ...

In my post of June 24 I requested some help on a sum (among other things). In particular, we had a summation result that we were using in ...

I finished reading two very different books about two theories in physics, The Age of Entanglement: When Quantum Physics Was Reborn by Loui...

Guest post by Aaron Sterling I attended DNA 15 , the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-...

I have two requests from my readers. Both are essentially help tracking things down. First : We (Bill Gasarch, Clyde Kruskal, Justin Krusk...

Jon Katz has a blog Random Bits We've put it on our blogroll. What will it be about? To quote Jon himself: The blog will cover rand...

I'm honored to have been elected as the new chair of SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. The re...

Google is celebrating the 10th anniversary of Blogger by asking its users  to write the stories of their blogs. I'll bite as this blog h...

A reader asks Can we define a class NNC such that NC ⊆ RNC ⊆ NNC. Is NNC known by some other name? It is clear that NNC ⊆ NP, but the rever...

(Our blog has ALWAYS been green.) This is a continuation of the topic in this blog entry . In the June 17, 2009 issue of The New Republi...

We present some PURE math that was APPLIED in a real way. I am more surprised by these things than I should be. Recall that a summation ...

(Guest Post by Samir Khuller.) I have noticed that even though in the 80's and 90's a large number of FOCS, STOC, and SODA papers...

My Kindle DX  arrived yesterday. I loved my first Kindle which I used for reading books and the New York Times. But the Kindle couldn't...

In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization , Russell alluded to a controversy with his ea...

Consider the following cute problem: Alice, Bob, and Carol each have a number between 0 and 1,000,000,000,000 on their forehead. Everyone ...

I finally succumbed to Twitter. I plan to use my twitter account to supplement the blog with bite-sized items. I may sometimes expand those...

Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true: ...

Tragic news from Jennifer Widom via Paul Beame. I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away ...

The other bloggers have done such a great job covering STOC that I won't add anything, except to say that I agree most of whats been sai...

One of Northwestern's professors made quite a splash a month ago with his group's predictions on the spread of the Swine Flu (now ca...