Probabilistic algorithms for sparse polynomials

By R. Zippel. 1979

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, background): “Similar arguments may rule out space-efficient AFE constructions for other natural functions.”
Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al. (2018, methodology): “8) Proof of Existence of P: Similar to the proof of existence of Cn matrices presented earlier, this proof of existence will use Schwartz-Zippel lemma [11], [12] about the roots of a polynomial.”
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al (2017, methodology): “c), C 4A [k] 4 (Wkc) are independent. Claim. The Cn satisfying the two required properties exist over Fp for a suﬃciently large prime p.6 Proof: This proof of existence will use Schwartz-Zippel lemma [9, 10] about the roots of a polynomial. The variables for the polynomial are the coeﬃcients of the ”
Randomized algorithms (1995, unknown): “Although it is usually attributed to the independent and simultaneous articles by Schwartz [367] and Zippel [422], essentially the same result appears in an article by DeMilio and Lipton [123] on the testing of algebraic programs.”
Handbook of Finite Fields (2013, methodology): “62 Remark Since polynomials represented by straight-line programs can be converted to sparse polynomials in polynomial-time in their sparse size by the algorithm in [Zippel 1979], the straight-line factorization algorithm brought to a successful conclusion the search for polynomial-time sparse facto”
Randomized Matrix Computations (2012, unknown): “es The total degree of a multivariate monomial is the sum of its degrees in all its variables. The total degree of a polynomial is the maximal total degree of its monomials. Lemma 3.1. [DL78], [S80], [Z79]. For a set ∆ of a cardinality |∆| in any ﬁxed ring let a polynomial in m variables have a tota”
A Gröbner Free Alternative for Polynomial System Solving (2001, methodology): “In [45, Theorem 5] it is shown using Zippel-Schwartz’s equality test [85, 72] that the choices can be done at random in a set of integers of size polynomial in the sequential complexity of AN ,L,C with a uniformly bounded probability of failure less than 1/2.”
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds (2003, methodology): “The importance of this problem is witnessed by a plethora of its applications to perfect matching [35, 37, 14], equivalence testing of read-once branching programs [10], multiset equality testing [11], primality testing [1, 2], a number of complexity-theoretic results on probabilistically checkable ”
Introduction to Property Testing (2017, background): “1 (The Schwartz–Zippel Lemma [250, 276, 86]): Prove the following two claims.”