What Are Proofs For Anyway?
How to make a polygon convex and how not to prove it Paul Cohen was one of the great logicians of the last century, who won the Fields Medal in 1966 for this brilliant work. He, of course, revolutionized set theory when he proved that the Axiom of Choice and the Continuum Hypothesis were both unprovable in the standard formal system called

New Streaming Algorithms for Old Problems
A streaming algorithm for the classic Dyck language Claire Mathieu, previously Claire Kenyon, is an expert in the design and analysis of algorithms, which should be no surprise since she worked as a graduate student with two of the world’s best—Philippe Flajolet and Jeffrey Vitter. Claire has done and continues to do some very pretty work on all aspects of algorithms. Today I

Nash Equilibrium for Sparse Games: Part Deux
How to find approximate Nash equilibrium for sparse games Constantinos Daskalakis is one of the experts in modern game theory, especially the structure of Nash Equilibrium for non-zero sum games. He has written a wonderful paper with Christos Papadimitriou On oblivious PTAS’s for nash equilibrium. Also see his nice

More on Mathematical Diseases
A summary of some your ideas on mathematical diseases John Conway is a world renowned mathematician, who defies a simple description. He has worked on countless games, puzzles, and easy to state, but often hard—if not impossible—to solve problems. These range from his classic game of Life, to his work on Surreal numbers; from his work on polyhedra, to his special notation for huge numbers. At the same time he has ma

Rumors and Playing Games
A rumor from FOCS on approximate Nash Equilibrium is partially true Paul Spirakis is a senior researcher who has made many important contributions to theory. He has hundreds of publications that cover many areas of theory. What is so impressive about Paul is that he has been able to blend theory and practice in a very fruitful way. This is a pretty unique skill that few have. Today I want to talk about a new result of his on finding approximate Nash E