Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR24-041 | 1st March 2024 22:41

Launching Identity Testing into (Bounded) Space



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.

ISSN 1433-8092 | Imprint