Browsing by Advisor "Saha, Chandan"
Now showing items 1-8 of 8
-
Equivalence test for the trace iterated matrix multiplication polynomial
An m-variate polynomial f is affine equivalent to an n-variate polynomial g if m > n and there is a full rank n * m matrix A and a n-dimensional 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
(2018-05-29)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 Multi-r-ic Depth Four Circuits as a Function of the Number of Input Variables
In this work we study the multi-r-ic formula model introduced by [KS15c] and improve upon the lower bound for multi-r-ic 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 Orbits and Border of Constant Read Circuits and Lower Bounds for Constant Depth Circuits
Two of the most common ways in which arithmetic circuits can be restricted is by requiring that they be constant read or constant depth. Constant depth circuits have received a lot of attention in the arithmetic circuit ... -
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 Nisan-Wigderson Polynomial Family
(2018-07-09)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 ...