Hitting Sets for Orbits of Circuit Classes

Vishwas Bhargava
Vidya Sagar Sharma
Friday, 28 May 2021, 17:15 to 18:15
The \emph{orbit} of an n-variate polynomial f(\var x) over a field \F, denoted by \orbit{f}, is the set of polynomials obtained by applying invertible affine transformations on the variables of f(\var x), and the orbit of a polynomial class is the union of orbits of all the polynomials in it.

In this talk, we will discuss recent progress on designing hitting sets for orbits of various circuit classes. In particular, we will discuss improved construction of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs).

Joint work with Sumata Ghosh (IIT-B).

Zoom link: