#### 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.