Computational Complexity

The 17x17 challenge: worth $289.00. I am not kidding. Definition: The n x m grid is c-colorable if there is a way to c-color the vertic...

First a message from David Johnson for proposals on locations for SODA 2012 both in and outside the US. Here's an interesting approac...

Last Friday DIMACS celebrated its 20th anniversary. Muthu summarizes the event. DIMACS  has served the theoretical computer science comm...

As most of you know there are 7 problems worth $1,000,000 (see here ). It may be just 6 since Poincare's conjecture has probably been s...

A student asked me which version of a research paper to cite, a journal (the last reviewed version) or a conference (the first reviewed vers...

There are now bibles online where you can click for different versions, different translations, different interepretations, historical conte...

As I tweeted yesterday, the videos of talks  from the  2009 FOCS conference  are now online. Thanks to FOCS PC chair Daniel Spielman and Ge...

As a young kid in the Reform Jewish community we used the Union Prayer Book, a traditional book with Hebrew on the right and English on the ...

There are now laws about blogging and twittering that Lance and I (and all the bloggers) will need to be aware of. Here is a short summary:...

As many university's still feel the effect of the financial crises, many have limited or no positions to hire new tenure-track faculty s...

Many of you readers don't remember a time when there were two Germanys or when we didn't think IP = PSPACE. Two walls collapsed in N...

IBM-NYU-COLUMBIA theory day on Dec 11 ! Here are pointers to more information: here and here and here . My advice: If you are a...

Guest Post from Aaron Sterling Multi-Agent Biological Systems and the Natural Algorithms Workshop I attended the Natural Algorithms ...

Back in 1993 I had the following conversation with one of my relatives: BILL: Just give me your email address and I'll email it to y...

Here is the offer: If you press the button you will receive $200,000. The caveat: Someone you don't know will die. I was born during r...

The new Innovations in Computer Science conference announced their accepted papers earlier this week including my paper with Rahul Santha...

Amir Pnueli passed away Monday from a brain hemorrhage. Amir was an expert in program verification who won the 1996 Turing Award primarily ...

(Reminder: STOC Deadline Thursday Nov 5, 7:00PM, Eastern: link .) After yesterday's post about RaTLoCC 2009 (Ramsey Theory in Logic...

Back from RaTLoCC 2009 which is Ramsey Theory in Logic, Combinatorics, and Complexity. Here are the list of talks: here . Reverse Math...

Last month I suggested that students should go to FOCS even if they didn't have a paper there. I doubt my post had much to do with it, ...