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 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 principle" 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.
Our number-one terminological misstep, in my view: "NP". I have at least twice winced to see this misidentified (in print and by other scientists) with "non-polynomial time", i.e. with the entire gnarly mess *outside* P.
ReplyDeleteThe situation is additionally bad because correcting that impression requires unpacking 'nondeterminism' for people--a fruitful notion, but much more conceptually difficult than the proof-checking or nonzero-acceptance-probability definitions of NP . I would've gone with 'PV' for 'polynomial verification'.
I also would've wanted to bring the more general, more comprehensible, and more a priori-significant 'lower bounds problem' into the forefront via better buzzwords. P vs NP takes pride of place among lower bound investigations, but (I would argue) this is by virtue of its discovered panoply of important complete problems, not because computer scientists are obsessed with pinpointing the power of a magical resource.
It mentions requiring 9 points in convex position (assuming I didn't misunderstand). Does this result dependon the other result that for any n a sufficient number of points on the plane will have n points in convex position? If so, what is the best known lower bound for n=9?
ReplyDeleteTo answer Bram's comment, yes it does depend on the old Erdos-Szekeres result (actually the result itself, rather than their version of it). I believe the range in Gerken's proof is that n > 500 and is less than 2000. Pavel Valtr has a simpler proof, but with a weaker bound.
ReplyDeleten <= (2*9-5 choose 9-2) = (13 choose 7) + 2 = 1718
ReplyDeleteShouldn't it be "principle" instead of "principal" ?
ReplyDeleteThanks. Fixed.
ReplyDeleteThe article of Lisa Randall has appeared in The New York Times rather than the Times.
ReplyDelete