Hitting Sets for Orbits of Circuit Classes

Speaker:
Vishwas Bhargava
Organiser:
Vidya Sagar Sharma
Date:
Friday, 28 May 2021, 17:15 to 18:15
Abstract
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:
https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09