Join us in person in 4403 Siebel Center for Computer Science or Online.
Abstract:
Polynomial identity testing (PIT) is the problem of deciding whether a multivariate polynomial, given in the form of an arithmetic formula or circuit, is identically zero. PIT has a simple efficient randomized algorithm: Pick a random point and check whether the polynomial is zero on that particular point.
Despite the fundamental nature of PIT and the simplicity of the randomized algorithm, no efficient deterministic algorithm is known. The quest for such an algorithm has intricate ties to circuit complexity, and results suggest that such an algorithm would allow us to efficiently derandomize every randomized decision algorithm with bounded error.
Much progress has been made in derandomizing PIT for interesting but restricted classes C of formulas and circuits. The standard approach consists of applying a substitution G that replaces each of the variables by a low-degree polynomial in a small set of fresh variables such that, for every nonzero polynomial p from C, p(G) remains nonzero. The bulk of the work then consists of (often ad-hoc) arguments establishing the latter property for the specific class C under consideration.
We propose a systematic approach that focuses on the substitution G and determines the set of polynomials p for which p(G) is identically zero. We execute the approach for one of the most widely used substitutions G, representing an algebraic equivalent of the notion of k-wise independence. One of the conceptual lessons of our study is that, even though polynomial substitutions G are provably sufficient, it is nevertheless beneficial to consider rational substitutions, as well.
Based on joint work with Andrew Morgan. ITCS 2022. https://arxiv.org/abs/2211.01062.
