![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||
|
The article does not identify Schwartz and Zippel after whome the lemma was named. Can anyone help? DFH 18:24, 26 January 2007 (UTC)
The link does not work. Moreover, Lipton's blog (mentioned in the references) mentions (and links to) a much earlier conference paper by Zippel from around 1979 (no precise reference, however) -- GuenterRote ( talk) 17:22, 15 January 2013 (UTC)
Couldn't the title be simplified to merely Schwartz-Zippel lemma? DFH 18:27, 26 January 2007 (UTC)
Or should the article be moved to Schwartz-Zippel theorem, which is currently a redirect to here. DFH 18:31, 26 January 2007 (UTC)
The Tutte polynomial is not the determinant of the Tutte matrix. Richard Pinch ( talk) 19:40, 5 July 2008 (UTC)
A binary decision diagram is used to encode boolean formulas, not arithmetic polynomials. The correct data structure should be arithmetic circuits.
128.178.77.113 ( talk) 15:53, 14 December 2009 (UTC)
Can someone place the citation to the original proof that read once branching programs represents a polynomial. Or at least, state what a read once branching program is, and give the idea of the translation branching program to polynomial. Presumably the reason you need read once is clear from the translation? — Preceding unsigned comment added by 136.159.93.148 ( talk) 16:44, 15 August 2014 (UTC)
This page not only describes the SZ-Theorem, but also includes long explanations on polynomial idendity testing. PIT is an important branch of research in computational complexity theory, therefore it is worth having its own article. Does anyone disagree? -- RedZiz ( talk) 22:54, 8 January 2010 (UTC)
There's a beautiful recent proof by Dana Moshkovitz, here. It avoids induction, and gives more intuition. Unfortunately it works only for the (most commonly used) case where S is the entire field. Could/should we use it in the article? Shreevatsa ( talk) 04:54, 5 July 2010 (UTC)
It would be nice to know what complexity classes the algorithms presented under "applications" yield for the given problems. AmirOnWiki ( talk) 13:24, 11 December 2011 (UTC)
I believe that there is an error in the proof section. It should say "This is because the degree of is at most d" instead of "This is because the degree of is at most d" -- ManosKouk89 ( talk) 14:24, 3 October 2012 (UTC)
Created a new page, since there's more to be said about polynomial identity testing than just the Schwartz–Zippel lemma. Rolf H Nelson ( talk) 03:59, 13 April 2016 (UTC)
The section contains (only) this: "Let p(x1,x2,...,xn) be the determinant of the polynomial matrix. Currently, there is no known sub-exponential time algorithm that can solve this problem deterministically. However, there are randomized polynomial algorithms whose analysis requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points." What polynomial matrix is "the" polynomial matrix? What problem is "this problem"? 2600:4040:2642:4800:8F21:8C0:B100:4A85 ( talk) 20:32, 24 August 2023 (UTC)
![]() | This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||||
|
The article does not identify Schwartz and Zippel after whome the lemma was named. Can anyone help? DFH 18:24, 26 January 2007 (UTC)
The link does not work. Moreover, Lipton's blog (mentioned in the references) mentions (and links to) a much earlier conference paper by Zippel from around 1979 (no precise reference, however) -- GuenterRote ( talk) 17:22, 15 January 2013 (UTC)
Couldn't the title be simplified to merely Schwartz-Zippel lemma? DFH 18:27, 26 January 2007 (UTC)
Or should the article be moved to Schwartz-Zippel theorem, which is currently a redirect to here. DFH 18:31, 26 January 2007 (UTC)
The Tutte polynomial is not the determinant of the Tutte matrix. Richard Pinch ( talk) 19:40, 5 July 2008 (UTC)
A binary decision diagram is used to encode boolean formulas, not arithmetic polynomials. The correct data structure should be arithmetic circuits.
128.178.77.113 ( talk) 15:53, 14 December 2009 (UTC)
Can someone place the citation to the original proof that read once branching programs represents a polynomial. Or at least, state what a read once branching program is, and give the idea of the translation branching program to polynomial. Presumably the reason you need read once is clear from the translation? — Preceding unsigned comment added by 136.159.93.148 ( talk) 16:44, 15 August 2014 (UTC)
This page not only describes the SZ-Theorem, but also includes long explanations on polynomial idendity testing. PIT is an important branch of research in computational complexity theory, therefore it is worth having its own article. Does anyone disagree? -- RedZiz ( talk) 22:54, 8 January 2010 (UTC)
There's a beautiful recent proof by Dana Moshkovitz, here. It avoids induction, and gives more intuition. Unfortunately it works only for the (most commonly used) case where S is the entire field. Could/should we use it in the article? Shreevatsa ( talk) 04:54, 5 July 2010 (UTC)
It would be nice to know what complexity classes the algorithms presented under "applications" yield for the given problems. AmirOnWiki ( talk) 13:24, 11 December 2011 (UTC)
I believe that there is an error in the proof section. It should say "This is because the degree of is at most d" instead of "This is because the degree of is at most d" -- ManosKouk89 ( talk) 14:24, 3 October 2012 (UTC)
Created a new page, since there's more to be said about polynomial identity testing than just the Schwartz–Zippel lemma. Rolf H Nelson ( talk) 03:59, 13 April 2016 (UTC)
The section contains (only) this: "Let p(x1,x2,...,xn) be the determinant of the polynomial matrix. Currently, there is no known sub-exponential time algorithm that can solve this problem deterministically. However, there are randomized polynomial algorithms whose analysis requires a bound on the probability that a non-zero polynomial will have roots at randomly selected test points." What polynomial matrix is "the" polynomial matrix? What problem is "this problem"? 2600:4040:2642:4800:8F21:8C0:B100:4A85 ( talk) 20:32, 24 August 2023 (UTC)