Seminar Details
Complete Derandomization of Identity Testing of Read-Once Formulas
- Start Date: February 28, 2018
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): IIya Volkovich - University of Michigan
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Presentation Type: Stand Alone Presentation
- Abstract:
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 09'.
Joint work with Daniel Minahan.