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.
