Robin Moser gave one of the best STOC talks ever in his award-winning paper A Constructive Proof of the Lovász Local Lemma. Not only an amazing result but...
I haven't been to STOC/FOCS since FCRC in San Diego two years ago. Since then I dropped thirty pounds and got a haircut last week. Amazing how many people...
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 called H1N1). Dirk Brockmann...
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 said: Moser's talk and...
Tragic news from Jennifer Widom via Paul Beame. I am deeply saddened to inform the database community that Prof. Rajeev Motwani passed away Thursday night in a...
Mathematics and TCS are full of conjectures. Some are proven true, some are still not known. Most that have been resolved have been true: - Fermat's last...
I finally succumbed to Twitter. I plan to use my twitter account to supplement the blog with bite-sized items. It'll take me some time to figure this out, if I...
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 can see the numbers...
In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still...
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 handle mathematical...
(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 eventually appeared in...
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 &sumi=0&infin ai...
(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 Republic, in an article called ...
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 reverse is not ...
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 has become such a a large...
I'm honored to have been elected as the new chair of SIGACT, the ACM Special Interest Group on Algorithms and Computation Theory. The rest of the executive...
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 random topics, but especially...
I have two requests from my readers. Both are essentially help tracking things down. First: We (Bill Gasarch, Clyde Kruskal, Justin Kruskal) have in a paper of...
Guest post by Aaron Sterling I attended DNA 15, the 15th International Meeting on DNA Computing and Molecular Programming, held June 8-11, 2009, at the...
I finished reading two very different books about two theories in physics, The Age of Entanglement: When Quantum Physics Was Reborn by Louisa Gilder and...
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 a paper and we wanted...
The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities related to their...
May 28 should be Pi-day instead of March 14 since pi should be what we now call 2*pi (6.28...) since 2*pi comes up in more formulas than pi. (When I blogged...
Prahladh Harsha asked me to post the following announcement on the blog. I don't usually post announcements but this seems like an excellent opportunity to...
For this pre-Independence Day post Bill suggested I write about the math knowledge of our founding fathers or how "P=NP" will declare itself independent of...
Farrah Fawcett and Michael Jackson died the same day (June 25, 2009). - Who is the most famous pair of people that died the same day? While its hard to measure...
This week I'm at Stanford for the TARK and EC conferences co-located for the first time. Next week in Paris for Complexity. Also a shout out to ICALP in Rhodes...
Speedup for Natural Problems (Guest post by Hunter Monroe.) Blum proved speedup for an artificially constructed problem; this paper (arXiv link), (ECCC link)...
The 12th TARK and 10th EC conferences both are being held at Stanford this week, both look at questions relating economics and computer science and shared...
