Now showing items 1-7 of 7

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