Polynomial Identity Testing via Evaluation of Rational Functions
summary
Paper shows that the rational function evaluation generator is equivalent (up to variable rescaling) to the Shpilka–Volkovich generator and gives an explicit, polynomial-size generating set for its vanishing ideal formed by small determinant polynomials called elementary Vandermonde circulations. Provides a membership test using partial derivatives and zero substitutions, proves minimum nonzero degree L+1 and sparsity = C(K+L+2, K+1), derives ROABP width lower bounds growing with L, and uses a Laurent-series “zoom lemma” to certify nonvanishing.
AI-written summary · about
chapters (20)
- 0:00Polynomial Identity Testing
- 2:59Conceptual Contributions
- 4:53Technical Contribution #2
- 8:37Outline
- 8:59Shpilka-Volkovich Generator
- 10:25Rational Function Evaluation Generator
- 11:55Equivalence of SV with RFE
- 15:20Some Explicit Polynomials in the Vanishing Ideal of RFE
- 16:46Elementary Vandermonde Circulation (EVC)
- 17:43EVCs Generate the Vanishing Ideal of RFE
- 19:19Implications
- 20:27Membership Test for Multi-Linear Polynomials
- 21:53Completeness of Derivatives and Zero Substitutions
- 23:43Read-Once Oblivious Algebraic Branching Programs
- 25:32Proof of Concept: Derandomization for ROABPS
- 27:13Zoom Lemma for Multi-Linear Polynomials
- 29:43Alternating Algebra Representation
- 32:50Intuition from Network Flow
- 34:55Example
- 35:54Summary
related talks
22mVerifying the Equivalence of Parameterized Quantum Circuits
55mInequalities and Reductions for Nonzero Kronecker Coefficients
23mGenerating Programs for Polynomial Multiplication with Correctness Assurance
01h 19mTutorial 2: Algorithmic Invariant Theory
55mNon-commutative Computation
01h 01mTrue Complexity of Multilinear Systems
20mFormalizing polynomial laws and the universal divided power algebra
14mVerification of Algorithm and Code Generation for Signal Transforms