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...
Speedup for Natural Problems (Guest post by Hunter Monroe.) Blum proved speedup for an artificially constructed problem; this paper (arXiv link), (ECCC link)...
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...
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...
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...
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...
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...
The NSF has been getting very strict about having PIs (primary investigators) fill out an annual report listing publications and activities related to their...
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...
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...
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 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...
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'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...
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...
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 ...
(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 ...
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...
(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...
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...
In the STOC talk Russell Impagliazzo gave on his paper An Axiomatic Approach to Algebrization, Russell alluded to a controversy with his earlier still...
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...
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...
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...
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...
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...
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...
I don't go to many talks at STOC, I prefer hanging out in the hallways and talking with other attendees. But the best talk I saw so far was the first, Atri...
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...
