Skip to content Skip to navigation

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


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.

Ilya Volkovich

I am a faculty in the Computer Science and Engineering Division at the University of Michigan.
Previously, I was a Postdoctoral Research Associate (postdoc) in the Computer Science Department at Princeton University and the School of Mathematics at the Institute of Advanced Study.

I graduated my Ph.D. in Computer Science from Technion, Israel Institute of Technology in 2012, where I was fortunate to be advised by Amir Shpilka.

CoRE 301
Event Date: 
02/28/2018 - 11:00am
Pranjal Awasthi and Shubhangi Saraf
Event Type: 
University of Michigan.