Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR20-033 | 16th March 2020 18:02

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

RSS-Feed




Revision #1
Authors: Suryajith Chillara
Accepted on: 16th March 2020 18:02
Downloads: 20
Keywords: 


Abstract:

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 deteriorates as the value of $\delta$ increases. Further, the bound is superpolynomial only when $\delta$ is $o(d)$. It is natural to ask if the dependence on $\delta$ in the bound could be weakened. Towards this, in an earlier result [STACS, 2020], we showed that for all large enough integers $n$ and $d$ such that $d = \Theta(\log^2{n})$, any syntactic depth four circuit of bounded individual degree $\delta\leq n^{0.2}$ that computes $IMM_{n,d}$ must have size $n^{\Omega(\log{n})}$.

In this paper, we make further progress by proving that for all large enough integers $n$ and $d$, and absolute constants $a$ and $b$ such that $\omega(\log^2n)\leq d\leq n^{a}$, any syntactic depth four circuit of bounded individual degree $\delta\leq n^{b}$ that computes $IMM_{n,d}$ must have size $n^{\Omega(\sqrt{d})}$. Our bound is obtained by carefully adapting the proof of Kumar and Saraf [SIAM J. Computing, 2017] to the complexity measure introduced in our earlier work [STACS, 2020].



Changes to previous version:

Fixed some typos and added an appendix with missing proofs.


Paper:

TR20-033 | 12th March 2020 14:29

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





TR20-033
Authors: Suryajith Chillara
Publication: 12th March 2020 15:49
Downloads: 58
Keywords: 


Abstract:

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 deteriorates as the value of $\delta$ increases. Further, the bound is superpolynomial only when $\delta$ is $o(d)$. It is natural to ask if the dependence on $\delta$ in the bound could be weakened. Towards this, in an earlier result [STACS, 2020], we showed that for all large enough integers $n$ and $d$ such that $d = \Theta(\log^2{n})$, any syntactic depth four circuit of bounded individual degree $\delta\leq n^{0.2}$ that computes $IMM_{n,d}$ must have size $n^{\Omega(\log{n})}$.

In this paper, we make further progress by proving that for all large enough integers $n$ and $d$, and absolute constants $a$ and $b$ such that $\omega(\log^2n)\leq d\leq n^{a}$, any syntactic depth four circuit of bounded individual degree $\delta\leq n^{b}$ that computes $IMM_{n,d}$ must have size $n^{\Omega(\sqrt{d})}$. Our bound is obtained by carefully adapting the proof of Kumar and Saraf [SIAM J. Computing, 2017] to the complexity measure introduced in our earlier work [STACS, 2020].



ISSN 1433-8092 | Imprint