Computational Complexity

In the April CACM, George V. Neville-Neil wrote a column on a question about the foundations of computer science: In most areas of science ...

Announcements: STOC Early Registration closes on April 30. STOC itself is June 6,7,8. CCC Early Registration closes May 3. CCC itself ...

(REMINDERS: STOC Early Registration closes on April 30. CCC Early Registration closes May 3. EC Early Registration closes on May 6. ) ...

Since the beginning of complexity we talked about time complexity t(n) as a function of the input size. But it has been the inverse of this ...

If you want to find something out you can ask Google, ask an expert, or (if you have a blog) ask your readers. Google is the most common; ho...

On Monday Richard Lipton wrote a nice piece on the work of Emil Post, a famous logician who had great results and even greater questions in...

YouTube Link

Pangrams are sentences that contain every letter of the alphabet. The classic is The quick brown fox jumps over a lazy dog. (NOTE- I had ...

A reminder that registration for all three Cambridge conferences are now live: STOC (early registration deadline April 30), Complexity (...

The following is from an Ask Marilyn Column. I paraphrase this since its from memory. READER'S LETTER: I have heard of exams where y...

So I broke down and bought the iPad. Many people have asked whether the iPad is worth buying. The short answer: It will be. There are many...

Guest Post by Bernhard Haeupler The Lovász Local Lemma (LLL), slightly simplified, states that: Given a set of “bad” events, if for every ...

April 9 was Tom Lehrer's 82nd birthday! To celebrate I give you breaking news that a Tom L DVD was released April 13, 2010. It seems t...

Besides being tax day, Thursday is the deadline to decide where to attend graduate school. How should you choose? I've blogged on this t...

In discrete math (or other courses) we teach AND DERIVE the formula for 1+2+3+...+n. We then look at the sum 1 2 +2 2 +...+n 2 . Here there ...

In January I gave a Distinguished Lecture in the CS Department at the University of Alberta. In early March I gave essentially the same lect...

(Looking for a roomate for STOC. Check out this site. .) Baseball Season started this week. I want to point out that Baseball violates ...

In my April Fools Day Post I said the following: Here are problems that I believe can be solved with current techniques. That was ind...

Last fall I wrote  about the different focus on models and proofs in the Econ and CS theory communities. Today I'll focus on the purpose...

I don't remember what prompted it but about a month ago I tweeted Your paper might appear on Arxiv or ECCC , be widely read and even we...