School of Technology and Computer Science Seminars

Quasipolynomial Hitting Sets for Circuits With Restricted Parse Trees

by Anamay Tengse (School of Technology and Computer Science, TIFR)

Friday, October 6, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
The polynomial identity testing task is to determine whether a given circuit computes the zero polynomial. A hitting set for a class of circuits is a set of evaluation points such that any non-zero circuit from the class outputs a non-zero value on at least one of these points. Therefore finding hitting sets gives a PIT. The task of finding hitting sets for a class of circuits called \emph{Read-once Oblivious Algebraic Branching Programs (ROABPs)} is seen as an algebraic analogue of the derandomisation of randomised logspace computation.

Lagarde, Malod and Perifel recently introduced a class of non-commutative circuits whose commutative version subsumes ROABPs. We refer to this commutative class as \emph{Unique Parse Tree (UPT) set-multilinear circuits}. Intuitively, an algebraic circuit belongs to this class if \emph{all its monomials are computed identically}. In the talk we will begin by formally defining UPT set-multilinear circuits and then go into the construction of a quasi-polynomial sized hitting set for it. The construction closely follows a construction by Agrawal et al. that gives hitting sets for ROABPs and thus provides more insight into the technique used by them.

NOTE: No background on polynomial identity testing or algebraic circuits will be assumed.