Browsing Computer Science and Automation (CSA) by Subject "Arithmetic Circuits"
Now showing items 1-4 of 4
-
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 ...