期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-23
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Kayal, Saha and Tavenas [Theory of Computing, 2018] showed that for all large enough integers n and d such that d > ω(log n), any syntactic depth four circuit of bounded individual degree δ = o(d) that computes the Iterated Matrix Multiplication polynomial (IMMn,d) must have size n Ω √ d/δ . Unfortunately, this bound deteriorates as the value of δ increases. Further, the bound is superpolynomial only when δ is o(d). It is natural to ask if the dependence on δ 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 = Θ(log2 n), any syntactic depth four circuit of bounded individual degree δ 6 n 0.2 that computes IMMn,d must have size nΩ(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 ω(log2 n) 6 d 6 n a, any syntactic depth four circuit of bounded individual degree δ 6 n b that computes IMMn,d must have size nΩ( √ 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].
