Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with alternating algebra:
TR22-115 | 17th August 2022
Dieter van Melkebeek, Andrew Morgan

Polynomial Identity Testing via Evaluation of Rational Functions

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. Despite 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 ... more >>>

ISSN 1433-8092 | Imprint