Talks - Fall 2017

Complexity subsets pspace

Title

Speaker

Date

Time

Venue

Abstract

EXP(N+D) TIME ALGORITHMS FOR COMPUTING DIVISION, GCD AND IDENTITY TESTING OF POLYNOMIALS

Kartik Vinayak Kale

6Jul (Thu), 2017

10:40am to 11:15am

KD102

Polynomial Identity Testing (PIT) is the problem of checking whether a multivariate polynomial is identically zero, given as a blackbox or as an arithmetic circuit. There exists a randomized algorithm putting the problem in coRP, and derandomizing it has interesting implications in complexity theory.

Recent progress towards derandomizing PIT has reduced the problem of finding a quasi-polynomial time deterministic algorithm for PIT to the problem of finding a exp(n,d,D/d)-time deterministic algorithm for blackbox PIT of depth-4 circuits with bottom fan-in d and degree D over n variables.

In this thesis, we give a deterministic exp(n,d)-time algorithm for whitebox PIT of depth-4 circuits with top fan-in 2 and bottom fan-in d over n variables. In the process, we give an exp(n,d)-time algorithm to compute the GCD of two n-variate polynomials of degree d. We also give an exp(n,d)-time algorithm to compute the division of a polynomial f by another polynomial g if f completely divides g and report failure otherwise, for polynomials f,g of degree d over n variables.

ALL SESSIONS


Contact

Image

Sumanta Ghosh

Head Co-ordinator

Image

Rajendra Kumar

Co-ordinator

Image

Mahesh S R

Co-ordinator