tag:blogger.com,1999:blog-3722233.post5249513814893024180..comments2020-01-20T07:37:42.239-05:00Comments on Computational Complexity: Erdos Distance Problem SOLVED!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-627255509428441872011-01-05T20:55:04.508-05:002011-01-05T20:55:04.508-05:00Erdos Distance Problem- YES, I
should have said so...Erdos Distance Problem- YES, I<br />should have said something like<br />solved-within-a-log factor.<br /><br />I've even seen it stated as<br />showing g(n) \ge n^{2-ep} for<br />all ep>0. THAT version has been solved.<br /><br />Still very impressive and surprising.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50683656930069871472011-01-05T18:17:22.675-05:002011-01-05T18:17:22.675-05:00Isn't Erdos Distance currently at O(n/sqrt(log...Isn't Erdos Distance currently at O(n/sqrt(log n))≥g(n)≥Ω(n/log n)?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62422235972683666752010-11-29T13:01:56.357-05:002010-11-29T13:01:56.357-05:00Not completely solved- OH, yes,
that is correct. B...Not completely solved- OH, yes,<br />that is correct. But very close.<br /><br />As for the author- he told me that he<br />will try to get a line in about the problem<br />before it goes to press.<br />THe book will still be worthwhile as the proofs of the earlier results are easier and interesting.<br /><br />GASARCHGASARCHnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82548050183285101772010-11-23T08:42:32.859-05:002010-11-23T08:42:32.859-05:00doesn't sound SOLVED to medoesn't sound SOLVED to meAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1951582621635863302010-11-23T02:52:02.006-05:002010-11-23T02:52:02.006-05:00What's going to happen to the book, which is p...What's going to happen to the book, which is probably already printed?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68313081835291207492010-11-22T22:56:30.856-05:002010-11-22T22:56:30.856-05:00Regarding #2, one paper by Erdos explicitly mentio...Regarding #2, one paper by Erdos explicitly mentioning the conjecture is:<br /><br />P. Erdos, On some metric and combinatorial geometric problems, Discrete Mathematics, 60 (1986) 147-153.<br /><br />In the he abstract he calls it 'An old and probably very difficult conjecture'. He also offers $500 for a proof of it.Andrew Winslowhttp://www.cs.tufts.edu/~awinsl02noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81619295068574066422010-11-22T17:04:25.728-05:002010-11-22T17:04:25.728-05:00Dear Gil-
THANKS- I have inserted the paper into ...Dear Gil- <br />THANKS- I have inserted the paper into my website and also added it to the blog itself.<br /><br />GASARCHGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79070176944833163282010-11-22T15:29:53.086-05:002010-11-22T15:29:53.086-05:00Dear Bill
"all(?)"
Elekes Shamir paper ...Dear Bill<br />"all(?)" <br />Elekes Shamir paper seems missing<br />http://front.math.ucdavis.edu/1005.0982Gil Kalaihttp://gilkalai.wordpress.com/noreply@blogger.com