Browsing by Advisor "Saha, Chandan"
Now showing items 17 of 7

Equivalence test for the trace iterated matrix multiplication polynomial
An mvariate polynomial f is affine equivalent to an nvariate polynomial g if m > n and there is a full rank n * m matrix A and a ndimensional vector b such that f(x) = g(Ax + b). Given blackbox access to f and g (i.e ... 
Expanders in Arithmetic Circuit Lower Bound : Towards a Separation Between ROABPs and Multilinear Depth 3 Circuits
Consider the problem of Polynomial Identity Testing(PIT): we are given an arithmetic circuit computing a multivariate polynomial over some eld and we have to determine whether that polynomial is identically zero or not. ... 
An Improved Lower Bound for Depth four Arithmetic Circuits
(20180529)We study the problem of proving lower bounds for depth four arithmetic circuits. Depth four circuits have been receiving much attraction when it comes to recent circuit lower bound results, as a result of the series of ... 
An Improved Lower Bound for Multiric Depth Four Circuits as a Function of the Number of Input Variables
In this work we study the multiric formula model introduced by [KS15c] and improve upon the lower bound for multiric depth four circuits given in [KST16b], when viewed as a function of the number of input variables ... 
On Learning and Lower Bound Problems Related to the Iterated Matrix Multiplication Polynomial
The iterated matrix multiplication polynomial (IMM) of width w and length d is the 1x1 entry in the product of d square matrices of size w. The w^2d entries in the d matrices are distinct variables. In this thesis, we study ... 
On symmetries of and equivalence tests for two polynomial families and a circuit class
Two polynomials f, g ∈ F[x1, . . . , xn] over a field F are said to be equivalent if there exists an n×n invertible matrix A over F such that g = f(Ax), where x = (x1 · · · xn)T . The equivalence test (in short, ET) for ... 
Towards a Charcterization of the Symmetries of the NisanWigderson Polynomial Family
(20180709)Understanding the structure and complexity of a polynomial family is a fundamental problem of arithmetic circuit complexity. There are various approaches like studying the lower bounds, which deals with nding the smallest ...