tag:blogger.com,1999:blog-3722233.post8620539552489501155..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Thanks for the Fuzzy MemoriesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-82597050174344479882023-10-12T18:30:44.001-05:002023-10-12T18:30:44.001-05:00Adding this note here in case anyone come across t...Adding this note here in case anyone come across this in the future. A few years after this post, in MFCS '13 Buhrman, Fortnow, Hitchcock, and Loff (https://doi.org/10.1007/978-3-642-40313-2_23) proved that if SAT is reducible to a weighted threshold function then PH=P^NP. So, not quite as good as concluding P=NP, but at least still shows that PH would collapse.Joshua Grochowhttps://home.cs.colorado.edu/~jgrochow/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-705505901543682692009-10-17T02:00:59.234-05:002009-10-17T02:00:59.234-05:00What is the largest number that Schnorr factored w...What is the largest number that Schnorr factored with his method? 15? That might answer your question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79360122696185169992009-10-16T09:48:12.807-05:002009-10-16T09:48:12.807-05:00This probably is an out-of-context question but wh...This probably is an out-of-context question but what is your opinion about the correctness/validity of Schnorr's polynomial time factoring algorithm published recently.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58747539309606978782009-10-15T22:26:38.271-05:002009-10-15T22:26:38.271-05:00CI fellows finally announced on cifellows.orgCI fellows finally announced on cifellows.orgAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34550685821303138512009-10-15T22:20:00.517-05:002009-10-15T22:20:00.517-05:00The original problem that I heard from Lance was f...The original problem that I heard from Lance was for arbitrary vectors in R^n, not {0,1}^n. It does seem hard to get a negative dot product from two 0-1 vectors :)ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5924948397690892492009-10-15T15:49:34.719-05:002009-10-15T15:49:34.719-05:00Last anonymous: I don't think the comment was ...Last anonymous: I don't think the comment was "uncalled for", but, despite probably being true, I imagine it was a bit tongue-in-cheek.<br /><br />I think that the AKS Primes in P result has been: a) read thoroughly by enough people b) extended by enough people c) taught by enough people and d) is simple enough that at this point it is very unlikely to contain errors.<br /><br />(This probably happens with many popular results whose proofs are not particularly hairy.)<br /><br />--Anon. 3Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45356496119599194852009-10-15T14:49:07.235-05:002009-10-15T14:49:07.235-05:00Don't worry, Manindra's proof with Kayal a...<i>Don't worry, Manindra's proof with Kayal and Saxena that Primes are in P is still safe.</i><br /><br />This last bit is absolutely uncalled for. Mistakes can and does happen to everyone. Anyone who claims otherwise is either lying or does not do research.<br /><br />Just to cite a famous example, it took Poincare several papers to formulate the so called Poincare conjecture -- all of which (along with his other papers on algebraic topology) were erroneous.<br />See Dieudonne's beautiful exposition of Poincare's work in his "History of Algebraic and Differential Topology". Nevertheless, Poincare is accepted as the founder of the field of algebraic topology.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69685398894857371792009-10-15T12:32:02.252-05:002009-10-15T12:32:02.252-05:00Wim, just think of them as 0-1 vectors.Wim, just think of them as 0-1 vectors.ryanwhttps://www.blogger.com/profile/09644595632189419277noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88049426820318807352009-10-15T10:41:30.096-05:002009-10-15T10:41:30.096-05:00Is there a typo? It says "d_k⋅q_ij < 0&quo...Is there a typo? It says "d_k⋅q_ij < 0", but both are bit strings.Wim van Damhttps://www.blogger.com/profile/14484831637730978511noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45492601193751053742009-10-15T10:32:26.671-05:002009-10-15T10:32:26.671-05:00Can the theorem be recovered nevertheless? I.e. do...Can the theorem be recovered nevertheless? I.e. does SAT reducible to a weighted threshold function imply P=NP?Sashohttps://www.blogger.com/profile/09380390882603977159noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68680770989422543982009-10-15T07:02:33.280-05:002009-10-15T07:02:33.280-05:00I don't understand why there isn't more pr...I don't understand why there isn't more pressure on the authors to get their retraction published. Their failure to follow up has now wasted lots of people's time.Anonymousnoreply@blogger.com