Name
Title | ||
|---|---|---|
Complete Derandomization of Identity Testing and Reconstruction of Read-Once Formulas. |
Abstract | ||
|---|---|---|
In this article, we study the identity testing problem of arithmetic read-once formulas (ROFs) and some related models. An ROF is a formula (a circuit whose underlying graph is a tree) in which the operations are { +, × } 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 ROFs, 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 and Yolkovich [51].
|
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3196836 | TOCT |
Keywords | DocType | Volume |
Arithmetic circuit, arithmetic formula, circuit reconstruction, derandomization, identity testing | Conference | 10 |
Issue | ISSN | Citations |
3 | 1942-3454 | 1 |
PageRank | References | Authors |
0.35 | 31 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Daniel Minahan | 1 | 1 | 0.35 |
| Ilya Volkovich | 2 | 145 | 8.64 |