tag:blogger.com,1999:blog-3722233.post7841739031138975409..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: It works in practice, but does it work in theory (Pollard's Factorization algorithm)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-81321452521518413802016-03-04T05:10:03.745-06:002016-03-04T05:10:03.745-06:00I disagree with your conclusion. While it's tr...I disagree with your conclusion. While it's true that theoretical and applied work need different mentalities, in this case theoretical work needs to cast away the shackles of proof, that serve but to obstruct its view of the truth.Yuval Filmushttps://www.blogger.com/profile/08450062297306341505noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79243304403918890942016-02-29T19:33:18.141-06:002016-02-29T19:33:18.141-06:00yep, factoring is one of the great areas of applie...yep, factoring is one of the great areas of applied CS, which is not always taken seriously by theoreticians. am a huge fan myself. see also this recent writeup, <a href="https://vzn1.wordpress.com/2015/12/29/select-refs-and-big-tribute-to-empirical-cs-math/" rel="nofollow">applied (T)CS</a>Anonymoushttps://www.blogger.com/profile/10048739391910999672noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11979290047142789682016-02-29T17:54:09.452-06:002016-02-29T17:54:09.452-06:00For discrete logs I think it is no longer the case...For discrete logs I think it is no longer the case that one only searches for algorithms `that work' (which to my mind implies a rigorous algorithm in any case) and is not concerned with provability. <br /><br />In particular, at the risk of being accused of shameless self-promotion, the following paper proposes a quasi-polynomial algorithm for the discrete log problem in fixed characteristic fields which is proven for infinitely many extension degrees, and subject to a single conjecture on field representations of a particular type, works for all extension degrees: http://arxiv.org/abs/1507.01495<br /><br />The algorithm is also very practical, which goes against the usual `rigorous is slower' rule of thumb, so it is not the case that theoretical and applied work need pull in different directions.Rob Grangerhttps://www.blogger.com/profile/16878835474871745984noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18699820368310138802016-02-29T09:43:07.500-06:002016-02-29T09:43:07.500-06:00Eric Bach did make some basic progress on analyzin...Eric Bach did make some basic progress on analyzing Pollard's algorithm rigorously: http://www.sciencedirect.com/science/article/pii/089054019190001I.Huckhttps://www.blogger.com/profile/08595162060649968471noreply@blogger.com