[Computational Complexity] Short Takes
Congratulations to Jon Kleinberg, theory's newest genius.
Suresh reports that Tobias Gerken has shown that given any large enough set of points in the plane in general position (no three colinear), six of them form a convex hexagon containing none of the others. That is a geometry theorem even I can even understand.
Sanjeev Arora gives an update on the SIGACT funding committee. I foresee very lengthy STOC and FOCS business meetings.
Lisa Randall, Harvard physicist and sister of CS theorist Dana Randall, wrote an op-ed piece in the Times on how scientific terms like "relativity", "uncertainty principal" and "global warming" often give the public the wrong impression of these concepts. Personally I would be excited if the general public knew enough about computational complexity to misunderstand it.
Posted by Lance to Computational Complexity at 9/20/2005 08:33:00 AM
Boaz Barak reports that Bernard Chazelle has updated his essay The Algorithm: Idiom of Modern Science complete with bells, whistles, cartoons, PCP's and zero knowledge.
Sanjeev Arora and Boaz are nearing completion of their complexity book and they need your help. Please send them comments big and small. They particularly need you readers who are not (yet) experts in complexity to gauge the readability of the text.
The Royal Society has placed all of their journals online with free access through December. Their archives go back to '65 (that's 1665) in case you want to read Ben Franklin's paper on electricity.
Posted by Lance to Computational Complexity at 9/21/2006 07:11:00 AM