Talks - Fall 2017

ArithmeticCircuit

Title

Speaker

Date

Time

Venue

Abstract

ON HITTING SETS FOR SPECIAL DEPTH-4 CIRCUITS

Pranav Bisht

6Jul (Thu), 2017

10am to 10:35am

KD102

We study the Polynomial Identity Testing (PIT) problem in this thesis. When an input multivariate polynomial f of n variables and degree d is given in the form of an arithmetic circuit of size s, it asks for an efficient algorithm to test whether the polynomial is identically zero or not. By efficient, we mean an algorithm that makes use of only poly(s,n,d) many field operations. We give an efficient blackbox PIT algorithm for the special class of diagonal depth 4 circuits, with top fan-in 3 and power gates having equal fan-in. We essentially use sparse PIT map to efficiently test whether f_1^a + f_2^a = f_3^a, where f_1, f_2 and f_3 are sparse polynomials. We use the polynomial analog of Fermat's Last Theorem to prove the correctness of our algorithm.

We also explain a new form of rank concentration measure called cone closure. We observe that a general polynomial under a random shift has a cone closed basis, and give a simple proof for the same using the derivative operator. For small characteristic fields, we give a new meaningful definition for cone closure, as the old definition fails in this regime. We make use of a clever transformation to prove cone closed basis here.

Lastly, for a given set of linearly independent polynomials, we question the linear independence of their positive powers. We get the answer by proving a new theorem which tells that the powers of these linearly independent polynomials will almost always be linearly independent. We give a quadratic upper bound on the number of exceptions. This property has a surprisingly elementary proof, making use of the Wronskians.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator