Computational Complexity

New superhero movies like Superman Returns and X-Men: The Last Stand remind me of my one time comic book addiction. As a child, I liked to...

The list of accepted papers for FOCS 2006 has been posted. Since I was on the program committee I won't comment on the papers or the p...

A female professor once told a story of a student who asked her out on a date. After she politely declined, the student asked her if she co...

Bill Gasarch is giving away free copies of one of our papers. Get them while they last. I recently got in the postal mail REPRINTS of a rec...

May Edition After we saw several randomized algorithms for primality we needed a way to classify and analyze the power of probabilistic ...

As an academic I can't count how many different college campuses I have visited. Most US universities produce beautiful glossy maps to m...

Many professional couples can have problems finding jobs in the same city, but for academics the problem magnifies. Even big cities will hav...

Thomas Schwentick sends me a link to an h-number calculator maintained by Michael Schwartzbach. Jorge Hirsch developed the h-number or h...

This week I'm attending EC '06 , The 7th ACM Conference on Electronic Commerce in Ann Arbor. The name does not completely fit the co...

Lawrence Downes writes a New York Times opinion Edison, Unplugged talking about the beauty of listening to music recorded in the 20's a...

Fresh off a PC (Program Committee) meeting in NJ (no tellsies), I drove from IL to MI for EC where I was also on the PC. First I spent the ...

From Computing Like Gods by Jörn Grote Time travel circuits had been in the first stages of development, but even then it was clear that w...

A reader Osias asks About purported P vs NP solutions…I was wondering what if you, sooner or later, lets say, 10 years from now, solve your...

At the STOC Business Meeting Richard Karp gave a report from the SIGACT Funding Committee . Why does TCS [Theoretical Computer Science] h...

My kids watched one of the Disney Channel sitcoms and I caught the following exchange: Teacher: Do you want to hear the funniest computer ...

In 1964 the Association of American Universities passed the following resolution setting a May 1 deadline for hiring away faculty from othe...

Last night my daughters and I watched a New Jersey girl win the National Spelling Bee. The final three contestants were all females though ...

Another guest post by Bill Gasarch A colleague is going to visit for a short time and you want to get some research done. When does this ...

Perhaps the very first example one sees of the probabilistic method: Show there exists a graph on n vertices with no clique or independent s...

Who would have thought the next theoretical computer science powerhouse would have come from Atlanta? Georgia Tech this year has hired Santo...