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