TR24-041 Authors: Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

Publication: 1st March 2024 23:17

Downloads: 85

Keywords:

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).

First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient arithmetic formula evaluation procedure. Among other things, we observe that the results of Minahan-Volkovich (ACM Transactions on Computation Theory, 2018), Gurjar et. al. (Theory of Computing, 2017) and Agrawal et. al. (SIAM Journal of Computing, 2016) imply logspace PIT algorithms for read-once formulas, constant-width read-once oblivious branching programs, and bounded-transcendence degree depth-3 circuits, respectively.

However, since the best known blackbox PIT algorithms for the class of multilinear read-$k$ formulas are quasi-polynomial time, as shown in Anderson et. al. (Computational Complexity, 2015), our previous observation only yields a $O(\log^2n)$-space whitebox PIT algorithm. Our main result, thus, is the first $O(\log n)$-space PIT algorithm for multilinear read-twice formulas. We also extend this result to test if a given read-twice formula is equal to a given read-once formula.

Our technical contributions include the development of a space-efficient measure $\muell$ which is ``distilled'' from the result of Anderson et. al. (Computational Complexity, 2015) and can be used to reduce PIT for a read-$k$ formula to PIT for a sum of two read-$(k-1)$ formulas, in logarithmic space.

In addition, we show how to combine a space-efficient blackbox PIT algorithm for read-$(k-1)$ formulas together with a space-efficient whitebox PIT algorithm for read-$k$ formulas to test if a given read-$k$ formula is equal to a given read-$(k-1)$ formula.