Tata Institute of Fundamental Research
Hitting Sets for Orbits of Circuit Classes
STCS Student Seminar
Speaker:
Vishwas Bhargava (Ph.D. student at Rutgers)
Organiser:
Vidya Sagar Sharma
Date:
Friday, 28 May 2021, 17:15 to 18:15
Venue:
(Scan to add to calendar)
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
| Speaker: | Vishwas Bhargava (Ph.D. student at Rutgers) |
| Organiser: | Vidya Sagar Sharma |
| Date: | Friday, 28 May 2021, 17:15 to 18:15 |
| Venue: |
(Scan to add to calendar)
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
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