Speaker: |
Anamay Tengse |

Organiser: |
Prerona Chatterjee |

Date: |
Friday, 6 Oct 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.