LIPIcs.ICALP.2019.78.pdf
- Filesize: 0.51 MB
- 15 pages
Document
Towards Optimal Depth Reductions for Syntactically Multilinear Circuits
Authors
-
Part of:
Volume:
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-07-04
File
Document Identifiers
Acknowledgements
We are extremely thankful to Ben Rossman, who pointed us towards this question, and for many stimulating discussions at various stages of this work. We also thank Shubhangi Saraf, Amir Shpilka and Ben Lee Volk for many helpful conversations. Mrinal also thanks Prahladh Harsha for accommodating him in his apartment for a part of the visit to TIFR, where a part of this paper was written.
Cite As Get BibTex
Mrinal Kumar, Rafael Oliveira, and Ramprasad Saptharishi. Towards Optimal Depth Reductions for Syntactically Multilinear Circuits. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 78:1-78:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ICALP.2019.78
Abstract
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 syntactically multilinear (Sigma Pi Sigma Pi) circuit of size at most exp ({O (sqrt{n log n})}). For degree d = omega(n/log n), this improves upon the upper bound of exp ({O(sqrt{d}log n)}) obtained by Tavenas [Sébastien Tavenas, 2015] for general circuits, and is known to be asymptotically optimal in the exponent when d < n^{epsilon} for a small enough constant epsilon. Our upper bound matches the lower bound of exp ({Omega (sqrt{n log n})}) proved by Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009], and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.
More generally, we show that an n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth Delta of size at most exp inparen{O inparen{Delta * (n/log n)^{1/Delta} * log n}}. It follows from the lower bounds of Raz and Yehudayoff [Ran Raz and Amir Yehudayoff, 2009] that in general, for constant Delta, the exponent in this upper bound is tight and cannot be improved to o inparen{inparen{n/log n}^{1/Delta}* log n}.
Subject Classification
ACM Subject Classification
- Theory of computation → Circuit complexity
Keywords
- arithmetic circuits
- multilinear circuits
- depth reduction
- lower bounds
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Manindra Agrawal and V. Vinay. Arithmetic Circuits: A Chasm at Depth Four. In Proceedings of the \ifnumcomp2008<1966\nth\intcalcSub20081959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2008)\ifnumcomp2008<1975\nth\intcalcSub20081959 Annual Symposium on Switching and Automata Theory (SWAT 2008)\nth\intcalcSub20081959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 67-75, 2008. URL: http://dx.doi.org/10.1109/FOCS.2008.32.
- Eric Allender, Jia Jiao, Meena Mahajan, and V. Vinay. Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theoretical Computer Science, 209(1-2):47-86, 1998. URL: http://dx.doi.org/10.1016/S0304-3975(97)00227-2.
- Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. In CCC 2018, pages 1-16, 2018. http://arxiv.org/abs/1708.02037. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2018.11.
- Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, and V. Vinay. The Chasm at Depth Four, and Tensor Rank : Old results, new insights. CoRR, 2016. URL: http://arxiv.org/abs/1606.04200.
- Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Approaching the Chasm at Depth Four. Journal of the ACM, 61(6):33:1-33:16, 2014. Preliminary version in the \ifnumcomp2013<1996\nth\intcalcSub20131985 Annual Structure in Complexity Theory Conference (Structures 2013)\ifnumcomp2013<2015\nth\intcalcSub20131985 Annual IEEE Conference on Computational Complexity (CCC 2013)\nth\intcalcSub20131985 Annual Computational Complexity Conference (CCC 2013). URL: http://dx.doi.org/10.1145/2629541.
- Sumant Hegde and Chandan Saha. Improved Lower Bound for Multi-r-ic Depth Four Circuits as a Function of the Number of Input Variables. Proceedings of Indian National Science Academy, 83(4):907-922, 2017. URL: http://dx.doi.org/10.16943/ptinsa/2017/49224.
- Neeraj Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. In Electronic Colloquium on Computational Complexity (ECCC) TR12-081, 2012. URL: https://eccc.weizmann.ac.il/report/2012/081/.
- Pascal Koiran. Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theoretical Computer Science, 448:56-65, 2012. URL: http://dx.doi.org/10.1016/j.tcs.2012.03.041.
- Mrinal Kumar and Shubhangi Saraf. On the power of homogeneous depth 4 arithmetic circuits. In Proceedings of the \ifnumcomp2014<1966\nth\intcalcSub20141959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2014)\ifnumcomp2014<1975\nth\intcalcSub20141959 Annual Symposium on Switching and Automata Theory (SWAT 2014)\nth\intcalcSub20141959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014), pages 364-373, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.46.
- Ran Raz. Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size. J. ACM, 56(2):8:1-8:17, 2009. Preliminary version in the \nth\intcalcSub20041968 Annual ACM Symposium on Theory of Computing (STOC 2004). URL: http://dx.doi.org/10.1145/1502793.1502797.
- Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. Comput., 38(4):1624-1647, 2008. Preliminary version in the \ifnumcomp2007<1966\nth\intcalcSub20071959 Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 2007)\ifnumcomp2007<1975\nth\intcalcSub20071959 Annual Symposium on Switching and Automata Theory (SWAT 2007)\nth\intcalcSub20071959 Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007). URL: http://dx.doi.org/10.1137/070707932.
- Ran Raz and Amir Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171-207, 2009. Preliminary version in the \ifnumcomp2008<1996\nth\intcalcSub20081985 Annual Structure in Complexity Theory Conference (Structures 2008)\ifnumcomp2008<2015\nth\intcalcSub20081985 Annual IEEE Conference on Computational Complexity (CCC 2008)\nth\intcalcSub20081985 Annual Computational Complexity Conference (CCC 2008). URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
- Amir Shpilka and Amir Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. URL: http://dx.doi.org/10.1561/0400000039.
- Sébastien Tavenas. Improved bounds for reduction to depth 4 and depth 3. Inf. Comput., 240:2-11, 2015. Preliminary version in the \nth\intcalcSub20131975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 2013). URL: http://dx.doi.org/10.1016/j.ic.2014.09.004.
- Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput., 12(4):641-644, 1983. Preliminary version in the \nth\intcalcSub19811975 Internationl Symposium on the Mathematical Foundations of Computer Science (MFCS 1981). URL: http://dx.doi.org/10.1137/0212043.