### DIMACS Theory of Computing Seminar

Title: Complete Derandomization of Identity Testing of Read-Once Formulas

Speaker: ** Ilya Volkovich**, University of Michigan

Date: Wednesday, February 28, 2018 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

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.

See: https://sites.google.com/view/dimacs-theory-seminar/home