Who were Schwartz and Zippel?

edit

The article does not identify Schwartz and Zippel after whome the lemma was named. Can anyone help? DFH 18:24, 26 January 2007 (UTC)Reply

I've now linked Schwartz to the article on him, unfortunately there is no article on Richard Zippel. Momet (talk) 13:24, 15 June 2008 (UTC)Reply


(Zippel 1989) reference

edit

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)Reply

I agree. Lipton's blog clearly stated that the original paper was in 1979. Also, Arora-Barack's text mentioned that it was discovered by Demillo and Lipton in 1978, almost the same time, in this paper. It's also called Schwartz-Zippel-Demillo-Lipton Lemma (see Lipton's blog post).SummerRat (talk) 04:51, 8 June 2013 (UTC)Reply

Move page ?

edit

Couldn't the title be simplified to merely Schwartz-Zippel lemma? DFH 18:27, 26 January 2007 (UTC)Reply

I agree with the proposal.Momet (talk) 13:32, 15 June 2008 (UTC)Reply
Moved. It is commonly called the Schwartz–Zippel lemma, as opposed to Schwartz–Zippel theorem. --Robin (talk) 22:46, 19 August 2009 (UTC)Reply

Lemma or theorem?

edit

Or should the article be moved to Schwartz-Zippel theorem, which is currently a redirect to here. DFH 18:31, 26 January 2007 (UTC)Reply

Tutte polynomial

edit

The Tutte polynomial is not the determinant of the Tutte matrix. Richard Pinch (talk) 19:40, 5 July 2008 (UTC)Reply

Binary Decision Diagrams?

edit

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)Reply

Nope. A read-once branching program for a Boolean function f naturally represents a multilinear polynomial p which agrees with f on {0,1}-inputs, and due to the multilinearity, two such polynomials are equal if and only if the Boolean functions they compute are equal. Thus, the Schwartz–Zippel lemma can be used to efficiently test whether two read-once BDD compute the same function. It's not a way of representing arbitrary polynomials, rather it is an application of polynomial identity testing to Boolean functions. — Emil J. 16:18, 14 December 2009 (UTC)Reply

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)Reply

PIT and Schwartz-Zippel-Theorem

edit

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)Reply

If you feel there's enough material on polynomial identity testing here to split it to a new article, please be bold and go ahead. If you haven't split an article before, you might wish to read Wikipedia:Split#Procedure. --Robin (talk) 01:12, 9 January 2010 (UTC)Reply
It seems like there is a polynomial deterministic algorithm for PIT. (Not that this is likely to get practical soon, as with primality testing. But still, such results are very interesting from the view of computational/structural complexity.) Note though that I'm no expert on complexity (alas) and I've just read the abstract. It would be nice if someone more competent verified this and e.g. added a reference here. Neználek (talk) 10:18, 20 November 2013 (UTC)Reply

Alternative proof

edit

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)Reply

S being the entire field is actually a severe restriction, as it does not work in the most commonly used case of PIT over Z. The proof looks very nice, though there is one thing I don't understand: how do we know that g does not vanish on Fm? I don't see how to prove that without using the Schwartz–Zippel lemma in the first place (if WLOG d < |F|; otherwise it's not even true in general).—Emil J. 16:50, 6 July 2010 (UTC)Reply

Complexity Classes

edit

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)Reply

Small error in proof

edit

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)Reply

New page: polynomial identity testing

edit

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)Reply

Is something missing from the "Determinant of a matrix with polynomial entries" section?

edit

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)Reply

Asking the same question here. 193.137.102.254 (talk) 16:54, 9 May 2024 (UTC)Reply