Quick Links

First, a plug: Aaron Roth, a grad student at CMU is keeping up a cool, informative TCS blog that deserves to be on the map. Check it out, especially if you want an insider's perspective on the rapidly growing area broadly referred to as 'algorithmic game theory'.


Bill Gasarch has been posting a number of nice puzzles lately. A couple have served as direct illustrations of ideas I've tried to exposit here, so I thought I'd point to them as follow-ups. In both cases I tried to describe the connection within the comments section.

1) For readers who followed my two posts on statistical distance, Bill gave a CS puzzle (about the possibility of 'zero-knowledge distributed consensus') that is exemplary for the use of reasoning about distance between distributions.

2) Bill described variants on Van der Waerden's Theorem, one of the classic results that presaged ideas of Ramsey Theory. He asked about the relation between Van der Waerden's Theorem for the natural numbers and its immediate extension to the real numbers. In particular, is the latter simpler? In the comments, I describe how the idea of compactness in logic, exposited here a while back, can be used to derive VDW's theorem from its real-number version.