Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Complete Derandomization of Identity Testing of Read-Once Formulas
event speaker icon
Ilya Volkovic (University of Michigan)
event date icon
Wednesday, 28.12.2016, 12:30
event location icon
Taub 201
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 {+, ×} 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 09’.

Joint work with Daniel Minahan.