Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR16-171 | 3rd November 2016 23:07

#### Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas

TR16-171
Authors: Daniel Minahan, Ilya Volkovich
Publication: 4th November 2016 03:29
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.