Fast Probabilistic Algorithms for Verification of Polynomial Identities

By Jacob T. Schwartz. 1980

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “The servers now execute a variant of the SchwartzZippel randomized polynomial identity test [104, 126] to check whether this relation holds.”
Integral reduction with Kira 2.0 and finite field methods (2020, methodology): “Most of the failures are triggered by hitting accidental zeros with a probability based on the Schwartz-Zippel lemma [47, 57].”
Verifying Computations with Streaming Interactive Proofs (2011, methodology): “This is an instance of the SchwartzZippel polynomial equality testing procedure [24].”
Decoding of Interleaved Reed Solomon Codes over Noisy Data (2003, background): “It follows that det( ˆ A∗) (seen as a multivariate-polynomial) is not the zeropolynomial and thus, by Schwartz’s Lemma [ Sch80 ], it cannot be 0 in more than”
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds (2003, methodology): “By the well-known Schwartz-Zippel lemma [47, 59, 18], evaluating a degree d multivariate polynomial on an tuple of random elements from a finite subset S yields a probabilistic algorithm whose error probability is at most d/|S|.”
Property testing and its connection to learning and approximation (1996, background): “Finally, one invokes Schwarz s Lemma [Schwartz 1980], by which two such degree n polynomials can agree on at most n/q 1/n3 fraction of the domain.”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, background): “When W k is undesired, we have ∀ n, Interfering Symbols Are Dependent and Have Dimension at most N ( N − 1) − ( N − 2) : Consider the interfering symbols along the common vectors Therefore ( N − 2) interfering symbols are linear combinations of the other N 2 − 2 N + 2 symbols.”
Dimensions in program synthesis (2010, unknown): “This includes polynomials [61] and free boolean graphs [9].”
Maximum matchings via Gaussian elimination (2004, background): “4 follow from the following lemma due to Zippel [18] and Schwartz [16]”
A Protocol for Privately Reporting Ad Impressions at Scale (2016, background): “But the probability of finding a qi that will satisfy the equation has an upper bound of (4N)/S if there are S possibilities for each ai by the Schwartz lemma [40].”
Quantum Computation and Information (2006, unknown): “NPol [76, 67]”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, background): “Lemma 1 ( [32]) Let F be any field, and let f : Fm→ F be a nonzero polynomial of total degree d.”
Expansion in finite simple groups of Lie type (2013, background): “We need to recall the Schwartz-Zippel lemma [57]:”
Introduction to Property Testing (2017, background): “1 (The Schwartz–Zippel Lemma [250, 276, 86]): Prove the following two claims.”
The NP-Completeness Column: An Ongoing Guide (1982, unknown): “Schwartz [ 38 ] has shown that a simple randomized test for this problem has error probability less than 1/2, and can be iterated to reduce this probability to an - 4 -”
Homomorphic Signatures for Polynomial Functions (2011, background): “By Schwartz’s Lemma [38], for any such polynomial f and any y ∈ Fp there are at most d · pk−1 solutions ~x ∈ Fp to f(~x)− y = 0, which is exactly the condition for F to be d-solution-bounded.”