ECCC-Report TR16-171https://eccc.weizmann.ac.il/report/2016/171Comments and Revisions published for TR16-171en-usFri, 04 Nov 2016 03:29:26 +0200
Paper TR16-171
| Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas |
Daniel Minahan,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2016/171In this paper we study the identity testing problem of \emph{arithmetic read-once formulas} (ROF) and some related models. A read-once formula is formula (a circuit whose underlying graph is a tree) in which the
operations are $\set{+,\times}$ and such that every input variable labels at most one leaf. We obtain the first polynomial-time deterministic identity testing algorithm that operates in the black-box setting for read-once formulas, as well as some other related models. As an application, we obtain the first polynomial-time deterministic reconstruction algorithm for such formulas.
Our results are obtained by improving and extending the analysis of the algorithm of \cite{ShpilkaVolkovich15a}.Fri, 04 Nov 2016 03:29:26 +0200https://eccc.weizmann.ac.il/report/2016/171