tag:blogger.com,1999:blog-3722233.post115374698897988694..comments2024-03-27T19:58:17.387-05:00Comments on Computational Complexity: Favorite Theorems: The PermanentLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-91729020208390714902013-03-18T10:01:51.710-05:002013-03-18T10:01:51.710-05:00Another interesting result on the permanent:
Co...Another interesting result on the permanent: <br /><br />Computing Permanents over Fields of Characteristic 3: Where and Why It Becomes Difficult (extended abstract). FOCS 1996Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153899841980417862006-07-26T02:44:00.000-05:002006-07-26T02:44:00.000-05:00Another nice result on the permanent,also due to V...Another nice result on the permanent,<BR/>also due to Valiant, is its completeness<BR/>for the class VNP of "easily definable"<BR/>families of polynomials.<BR/>This implies that the permanent can be<BR/>evaluated in a polynomial number of arithmetic operations iff all <BR/>"easily definable" families of polynomials<BR/>can.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153784438268665982006-07-24T18:40:00.000-05:002006-07-24T18:40:00.000-05:00"Other nice results that are worth mentioning..."T..."Other nice results that are worth mentioning..."<BR/><BR/>The paper on Clifford algebras has a "result"? Who knew?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1153755402443045552006-07-24T10:36:00.000-05:002006-07-24T10:36:00.000-05:00Other nice results that are worth mentioning are "...Other nice results that are worth mentioning are <A HREF="http://www.cs.berkeley.edu/~sinclair/clifford.ps" REL="nofollow">"Clifford algebras and approximating the permanent"</A> and <A HREF="http://www.cs.berkeley.edu/~sinclair/perm2.ps" REL="nofollow">"A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries"</A>Anonymousnoreply@blogger.com