Friday, May 01, 2009

Foundations of Complexity

In the first year of this blog I wrote a series of "lessons" to give an informal introduction to computational complexity but I never wrote a single post that links to them all. 

6 comments:

  1. Does anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?

    ReplyDelete
  2. Does anyone know anything about the supposed ~60 postdocs that are to be announced via NSF stimulus funds? Is there an announcement yet?
    If you are referring to the 30 new stimulus funded NSF Math Institute postdoc positions -- these positions have already been been filled. I don't know where you got the number 60 from ?

    ReplyDelete
  3. The links are broken. Could they be fixed? They look like valuable material. Thanks

    ReplyDelete
  4. The links should have forwarded properly but I updated them just in case.

    ReplyDelete
  5. Can someone solve this communication complexity puzzle: Bob knows which two of 16 soccer teams played a game. His friend Alice knows who out of those 16 teams won the game (she doesn't know who the losing team was). What is the minimal amount of bits of information (0s and 1s) that must be communicated between Alice and Bob in order for Bob to find out who won?

    ReplyDelete