In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that...
How well known is the concept of the Turing Test? Readers of this blog know what it is. On Google it gets 2,360,000 hits. It has a Wikipedia entry: here. None...
I spent some time this weekend updating my publications page. I did well in the summer conference season: An ICALP paper and two each in Complexity and TARK....
As an MIT alum I have an automatic subscription to Technology Review, a pretty nice perk. Wrapped around the current issue was a note that I could trade my...
Dear Organizers of IBM Research|NYU|Columbia Theory Day, You emailed me the ad for Spring 2009 Theory Day. THANKS! You did this about a week ago. Hence, as is...
I measure academic age by years since Ph.D. and by that measure I just turned twenty. I passed my Ph.D. defense on May 5, 1989 (though technically I didn't...
The Computational Complexity has a new URL blog.computationalcomplexity.org. This change should increase reliability of posting, commenting and loading the...
A grad student recently asked me for some refs on probabilistic hypergraphs. I didn't know any, but I suggested we harness the power of the internet and of the...
A grad student asked me the following question about how to measure running times. A paper in POPL 08 claims to have broken the long-standing n3 barrier on a...
Recall the Prime Number Theorem (PNT). Let &pi(n) be the number of primes that are &le n. As n goes to infinity &pi(n) approaches n/ln(n). Note that we did not...
A few weeks ago my eighth-grade daughter learned about the quadratic formula for solving ax2+bx+c=0. She's impressed I can still rattle it off like a song...
About a month ago I came across a proof that HALT is undecidable in verse! I thought what a great post that would make! Last week I tried to find it again but,...
We just posted the talk schedule for the 2009 ACM Electronic Commerce Conference. Early registration deadline is June 12th and hotel deadline is June 5th. The...
MEM PROBLEM: Let n,U be such that n < < U. We want to do the following: For all sets A &sube {1,...,U} such that |A|=n we want to store A in s(n,U) cells...
This year's Gödel Prize has been awarded to two papers. - Undirected Connectivity in Log-Space by Omer Reingold - Entropy Waves, the Zig-Zag Graph Product and...
"Are you taking full advantage of President Obama's stimulus package?" asks a recent robocall. So are you? If not the National Science Foundation has some ways...
CLYDE: I met Raymond Smullyan in the around 1985. He was old then. When did he pass away? BILL: Lets look it up on Wikipedia. (He does.) OH, he didn't! He is ...
For a short time in the 70's, some believed that oracle results would lead to true independence results in computational complexity. Richard Lipton in his post...
My 11-year old daughter took a some courses on computer gaming that used the Greenfoot system and wrote a eco-themed game Trees (requires Java, click "play"...
I'm at the University of Wisconsin for the second FRG Workshop on Algorithmic Randomness. FRG stands for "Focused Research Group", in our case a 12 PI...
"I'm not keen on the hype" says Stephen Wolfram, this from the man whom I once heard exclaim "First there was Euclid. Then there Gödel. Then there was...
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...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
