Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-109 | 21st July 2023 23:20

Towards Identity Testing for Sums of Products of Read-Once and Multilinear Bounded-Read Formulae


Authors: Pranav Bisht, Nikhil Gupta, Ilya Volkovich
Publication: 23rd July 2023 15:21
Downloads: 254


An arithmetic formula is an arithmetic circuit where each gate has fan-out one. An \emph{arithmetic read-once formula} (ROF in short) is an arithmetic formula where each input variable labels at most one leaf. In this paper we present several efficient blackbox \emph{polynomial identity testing} (PIT) algorithms for some classes of polynomials related to read-once formulas. Namely, for polynomial of the form:

\item $f = \Phi_1 \cdot \ldots \cdot \Phi_m + \Psi_1 \cdot \ldots \cdot \Psi_r$, where $\Phi_i,\Psi_j$ are ROFs for every $i \in [m], j \in [r]$.

\item $f = \Phi_1^{e_1} + \Phi_2^{e_2} + \Phi_3^{e_3}$, where each $\Phi_i$ is an ROF and $e_i$-s are arbitrary positive integers.

Earlier, only a whitebox polynomial-time algorithm was known for the former class by Mahajan, Rao and Sreenivasaiah (Algorithmica 2016).

In the same paper, they also posed an open problem to come up with an efficient PIT algorithm for the class of polynomials of the form $f = \Phi_1^{e_1} + \Phi_2^{e_2} + \ldots + \Phi_k^{e_k}$, where each $\Phi_i$ is an ROF and $k$ is some constant. Our second result answers this partially by giving a polynomial-time algorithm when $k=3$. More generally, when each $\Phi_1,\Phi_2,\Phi_3$ is a multilinear bounded-read formulae, we also give a quasi-polynomial-time blackbox PIT algorithm.

Our main technique relies on the \emph{hardness of representation} approach introduced in Shpilka and Volkovich (Computational Complexity 2015). Specifically, we show hardness of representation for the resultant polynomial of two ROFs in our first result. For our second result, we lift hardness of representation for a sum of three ROFs to sum of their powers.

ISSN 1433-8092 | Imprint