Talks - Spring 2018

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

Tiny Depth-4 PIT suffices

Pranav Bisht

16th Feb,2018

5-6pm

KD102

We intend to discuss the second part (Theorem 4) of the recent paper "Bootstrapping variables in algebraic circuits" by Agrawal, Ghosh, Saxena (STOC'18). Last time, we discussed depth-reduction result of AV08 and realized that polynomial time PIT algorithm for just depth-4 circuits gives us a quasi-polynomial time PIT algorithm for general circuits. In other words, (poly(s), poly(s))-hsg (hitting set generator) for a size-s depth-4 circuit is sufficient for the PIT problem.

Theorem 4 of AGS'18 further strengthens this result, stating that an (poly(s), O( s^(n/2)/log^2(s) ) )-hsg for a polynomial computed by size-s depth-4 circuit over a constant number of variables - n >= 3 implies a quasi-polynomial time algorithm for general circuits. We note that (poly(s), O(s^n)-hsg is trivial, and we only need to find a hitting set whose size is slightly less than s^(n/2).

References:

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator