tag:blogger.com,1999:blog-3722233.post114804269141590547..comments2020-01-16T02:41:14.513-05:00Comments on Computational Complexity: Favorite Theorems: Primality AlgorithmsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-1148274824921298992006-05-22T01:13:00.000-04:002006-05-22T01:13:00.000-04:00As far as I am aware, the best running time withou...As far as I am aware, the best running time without any number-theoretic assumptions, and even without any deeper number-theory involved is (log n)^(10.5).<BR/><BR/>With Fouvry's theorem, they show an exponent of 7.5 in the Annals of Mathematics paper. Finally, AKS mention that Lenstra and Pomerance came up with a modified version of the AKS algorithm. They achieve a running-time with a 6 in the exponent.Bodo Mantheynoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148234951821230192006-05-21T14:09:00.000-04:002006-05-21T14:09:00.000-04:00There's a new undergrad algorithms text to come ou...There's a new undergrad algorithms text to come out soon. A draft is now at http://www.cse.ucsd.edu/users/dasgupta/mcgrawhill/ and appears to cover some quantum algorithms.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148189630465019112006-05-21T01:33:00.000-04:002006-05-21T01:33:00.000-04:00Has the Agrawal-Saxena-Kayal algorithm become more...Has the Agrawal-Saxena-Kayal algorithm become more efficient since it was published? As I know, they proved log^{12} n complexity under no assumptions and log^6 n under the Sophie Germain conjecture.Dmitry Khovratovichnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148049414165379812006-05-19T10:36:00.000-04:002006-05-19T10:36:00.000-04:00Paper athttp://www-cse.ucsd.edu/users/kabanets/Res...Paper at<BR/><BR/>http://www-cse.ucsd.edu/users/kabanets/Research/poly.htmlAndy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148049248516898122006-05-19T10:34:00.000-04:002006-05-19T10:34:00.000-04:00Identity testing for low-degree multivariate polyn...Identity testing for low-degree multivariate polynomials (given as formulas or as circuits): it's in coRP, since inequivalent low-degree polynomials disagree on 'most' points.<BR/><BR/>One important reason to try and derandomize this problem is shown by Impagliazzo and Kabanets: if it's in P then at least one of the following is true:<BR/><BR/>i) NEXP doesn't have polynomial sized boolean circuits; <BR/><BR/>ii) PERMANENT doesn't have *algebraic* poly-sized circuits.<BR/><BR/>The proof is very enjoyable as it uses the Theorems of Valiant, Toda, and Shamir as well as Nisan-Wigderson pseudorandom generators. <BR/><BR/>The use of the identity testing is this: if PERMANENT has small algebraic circuits and we're presented with them for all matrix sizes 1 thru n, then we can verify them probabilistically by the downwards-self-reducibility of the permanent (and PERM is in MA); with deterministic algebraic circuit equivalence testing we can strengthen this to 'PERM is in NP'. Then, using the assumption that NEXP has small circuits, it's shown that NEXP must be in the polynomial hierarchy (NEXP=MA), and since PERM is hard for the PH, NP = NEXP, which is impossible.Andy Dhttps://www.blogger.com/profile/03897281159810085972noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1148047041904837812006-05-19T09:57:00.000-04:002006-05-19T09:57:00.000-04:00So what's the best current example of something in...So what's the best current example of something in BPP (or RP, or coRP), not known to be in P?Anonymousnoreply@blogger.com