2026-07-24T05:11:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15715 2024-03-06T10:56:01Z ddc:004 open_access

Polynomial Identity Testing via Evaluation of Rational Functions van Melkebeek, Dieter Morgan, Andrew Derandomization Gröbner Basis Lower Bounds Polynomial Identity Testing We introduce a hitting set generator for Polynomial Identity Testing based on evaluations of low-degree univariate rational functions at abscissas associated with the variables. In spite of the univariate nature, we establish an equivalence up to rescaling with a generator introduced by Shpilka and Volkovich, which has a similar structure but uses multivariate polynomials in the abscissas. We study the power of the generator by characterizing its vanishing ideal, i.e., the set of polynomials that it fails to hit. Capitalizing on the univariate nature, we develop a small collection of polynomials that jointly produce the vanishing ideal. As corollaries, we obtain tight bounds on the minimum degree, sparseness, and partition size of set-multi-linearity in the vanishing ideal. Inspired by an alternating algebra representation, we develop a structured deterministic membership test for the vanishing ideal. As a proof of concept we rederive known derandomization results based on the generator by Shpilka and Volkovich, and present a new application for read-once oblivious arithmetic branching programs that provably transcends the usual combinatorial techniques. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dieter van Melkebeek and Andrew Morgan 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.119 urn:nbn:de:0030-drops-157158 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.119 eng https://creativecommons.org/licenses/by/4.0/legalcode