2026-07-22T13:50:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7512 2024-03-06T10:40:14Z ddc:004 open_access

Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas Minahan, Daniel Volkovich, Ilya Derandomization Read-Once Formulas Identity Testing Arithmetic Circuits Reconstruction In this paper we study the identity testing problem of 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 {+,x} 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 [Shpilka-Volkovich, 2015] Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Minahan and Ilya Volkovich 2017 Is Part Of LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2017.32 urn:nbn:de:0030-drops-75128 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.32 eng https://creativecommons.org/licenses/by/3.0/legalcode