Computational Complexity

The US tries again with a new series of one dollar coins but will again fail since we still have the dollar bill. I have heard calls for e...

The two-body problem , finding two academic jobs in the same city, is becoming an epidemic in American universities. Some administrators hav...

In the wake of a misleading Economist article on the D-Wave quantum computer, Scott argues why he believes quantum computers cannot effici...

The Economists have a Job Market Wiki listing interviews and offers in mostly academic economics departments. The wiki is far from complete...

A reader writes about coming across a 2003 CIO article about Google Research Director Monika Henzinger and being quite surprised to read t...

Frances Allen will receive the 2006 Turing Award (the most prestigious CS prize), the first woman to win the award (via USACM ).

I have received some questions recently asking me advice for topics on which I have previously posted. So here are links to postings to help...

As many of you already know, the accepted papers for STOC '07 has been posted. And in that great circle of theory life, the FOCS '...

Two quirky computer events over the vacation. I enter events in my online calendar in Lance-time, i.e., at the time in the time-zone I will...

Guest Posting for Guest Blogger Bill Gasarch, Guest Poster Clyde Kruskal. At my fathers memorial service, here is how I ended my remark...

Bill Gasarch again. Martin David Kruskal was a brilliant Mathematician who passed away in late December, at the age of 81. (His...

(Guest Blog by Bill Gasarch has has a large collection of novelty songs, mostly funny songs.) I) There was a satire on Saturday Night ...

READING PAPERS FOR FUN Bill Gasarch guest blogging for Lance Fortnow Jane: What you you been working on? Bill: I've come up with ...

I am on vacation and off the internet for most of next week. Bill Gasarch will bring you his wit and wisdom in my absence. A few of the acc...

As an undergrad at Cornell in the early 80's, I witnessed the movement to encourage the university to divest their endowment holdings in...

The president sent out his proposed budget for FY08 (starting October 1, 2007). The NSF in general and CS in particular do quite well. The C...

A reader asks You've told us what to wear and how to give the talk at my interview. Any tips for the rest of the trip? Aside from y...

I woke up to see one of my complexity submissions accepted. But soon the other two were rejected. Then the Bears lost. The list of accepte...

Only one topic dominates discussion in Chicago these days—the Bears in Super Bowl XLI , America's biggest sporting event. The Bears las...

Microsoft researcher and Turing award winner Jim Gray is missing at sea after taking his boat out on Sunday. The Coast Guard continues the...