Login
Talks & Seminars
Title: Low Variate Polynomials: Hitting Set and Bootstrapping
Sumanta Ghosh, IIT Kanpur
Date & Time: August 13, 2019 11:30
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
One central concept in complexity theory is Derandomization. Polynomial Identity Testing (PIT) problem is a good test case for that purpose. PIT problem asks to decide whether a given arithmetic circuit computes a zero polynomial. It has a polynomial time randomized algorithm. However, designing a *deterministic* polynomial time algorithm for PIT is a long-standing open question in complexity theory. In our work, we study PIT problem in the blackbox setting, where we are not allowed to see the internal structure of the circuit and only evaluation at points is allowed. Designing blackbox PIT algorithm is equivalent to finding a set of points, called hitting set, such that for every non-zero circuit the set contains a point where it evaluates a non-zero value. In a joint work with Manindra Agrawal and Nitin Saxena, we study the phenomenon of bootstrapping in PIT: converting a hitting set of size-s degree-s n(s)-variate circuits to hitting set of a size s degree s s-variate circuits, where n(s)<
Speaker Profile:
Sumanta Ghosh is a PhD student at IIT Kanpur under Prof. Nitin Saxena. His research interests are Algebraic Complexity Theory, Computational Number Theory and Algebra, and Combinatorial problems.
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback