Talk:Schwartz–Zippel lemma

Who were Schwartz and Zippel?

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

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)

(Zippel 1989) reference

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)

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)

Move page ?

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

I agree with the proposal.Momet (talk) 13:32, 15 June 2008 (UTC)

Moved. It is commonly called the Schwartz–Zippel lemma, as opposed to Schwartz–Zippel theorem. --Robin (talk) 22:46, 19 August 2009 (UTC)

Lemma or theorem?

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

Tutte polynomial

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

Binary Decision Diagrams?

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)

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)

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)

PIT and Schwartz-Zippel-Theorem

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)

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)

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)

Alternative proof

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)

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 F^m? 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)

Complexity Classes

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)

Small error in proof

I believe that there is an error in the proof section. It should say "This is because the degree of $x_{1}^{i}P_{i}$ is at most d" instead of "This is because the degree of $P_{i}$ is at most d" --ManosKouk89 (talk) 14:24, 3 October 2012 (UTC)

New page: polynomial identity testing

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)

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

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)

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