Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Bounded individual degree:
TR20-032 | 12th March 2020
Suryajith Chillara

On Computing Multilinear Polynomials Using Multi-r-ic Depth Four Circuits

Revisions: 2

In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of $r$ (referred to as multi-$r$-ic circuits). The goal of this study is to make progress towards proving ... more >>>

TR20-033 | 12th March 2020
Suryajith Chillara

New Exponential Size Lower Bounds against Depth Four Circuits of Bounded Individual Degree

Revisions: 1

Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers $n$ and $d$ such that $d\geq \omega(\log{n})$, any syntactic depth four circuit of bounded individual degree $\delta = o(d)$ that computes the Iterated Matrix Multiplication polynomial ($IMM_{n,d}$) must have size $n^{\Omega\left(\sqrt{d/\delta}\right)}$. Unfortunately, this bound ... more >>>

ISSN 1433-8092 | Imprint