Computational Complexity

Fresh back from my Israel trip, still slightly jet lagged, and several hundred emails await me. Hold on, I will get to yours soon. A new qu...

Today was UNIV OF MD GRAD VISIT DAY for computer science grad students. We invited the students who got into UNIV OF MD Grad School in Compu...

You can now register for Conference on Computational Complexity, 2008 which will be in College Park Maryland. Go here to register and also ...

I recently got the following email. It is not spam in that it is a legitimate company asking a fair question and it has only gone to a selec...

(Guest post from Richard Beigel, NSF Theory Director, paraphrased. Any bad spelling or grammar you can attribute to me.) Because of que...

Arthur C. Clarke passed away yesterday. Of course 2001  dominates peoples memory of Clarke, but it was one of his short stories, The Nine Bi...

Guest post by Nicole Immorlica We say goodbye this month to a profoundly inspiring mathematician and economist, David Gale . His influe...

One of my readers emailed me the question below. I gave some answers but then I thought Lets draw on the wisdom of my readers (EMAIL FRO...

This year I wrote one of the problems on the Univ of MD High School Programming Contest. The following conversation did not take place but c...

Our weblog has joined the Scientific American Partner Network. You won't see any changes in the blog (besides the logo). You will contin...

Every year about this time, Americans come together and argue and wage large amounts of money on the outcome of a simple binary tree known a...

Amazon has a feature where a reader can associate a word (called a tag ) to a book, really user-defined keywords. However, this can be abuse...

Mid-March is the time of year we begin to hear concern from students and postdocs on the job market. The CS job market is a lengthy affair r...

When discussing what should we teach in a basic complexity course (taken mostly by non-theorists) we often say results such-and-such is imp...

I recently watched a surprisingly good documentary The King of Kong: A Fistful of Quarters where Steve Wiebe tries to break the Donkey Kong...

(A commenter left an off-topic comment on my last entry. INSERT GENDER-NEUTRAL PRONOUN HERE SINCE I DO NOT KNOW GENDER OF COMMENTER raisesd...

If you are a big shot in the political world then endorsing a political candidate has a game theory flavor to it. I'm sure someone could...

I got this email and was NOT asked to blog about it, but should have been: Visions for Theoretical Computer Science Theoretical Com...

Someone on the job market was wondering how many classes they could skip teaching in a typical term. As this is generally not a good questio...

Consider the following game: A player starts with 0 points. For 100 rounds, a player picks one of the following three actions in each round....