ECCC-Report TR24-041https://eccc.weizmann.ac.il/report/2024/041Comments and Revisions published for TR24-041en-usFri, 01 Mar 2024 23:17:45 +0200
Paper TR24-041
| Launching Identity Testing into (Bounded) Space |
Nikhil Gupta,
Pranav Bisht,
Prajakta Nimbhorkar,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2024/041 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.Fri, 01 Mar 2024 23:17:45 +0200https://eccc.weizmann.ac.il/report/2024/041