Abstract
In this paper, we prove superpolynomial lower bounds for the class of homogeneous depth 4 arithmetic circuits. We give an explicit polynomial in VNP of degree n in n 2 variables such that any homogeneous depth 4 arithmetic circuit computing it must have size n Ω(loglogn).
Our results extend the works of Nisan-Wigderson [13] (which showed superpolynomial lower bounds for homogeneous depth 3 circuits), Gupta-Kamath-Kayal-Saptharishi and Kayal-Saha-Saptharishi [4, 7] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded bottom fan-in), Kumar-Saraf [9] (which showed superpolynomial lower bounds for homogeneous depth 4 circuits with bounded top fan-in) and Raz-Yehudayoff and Fournier-Limaye-Malod-Srinivasan [3, 14] (which showed superpolynomial lower bounds for multilinear depth 4 circuits). Several of these results in fact showed exponential lower bounds.
The main ingredient in our proof is a new complexity measure of bounded support shifted partial derivatives. This measure allows us to prove exponential lower bounds for homogeneous depth 4 circuits where all the monomials computed at the bottom layer have bounded support (but possibly unbounded degree/fan-in), strengthening the results of Gupta et al and Kayal et al [4, 7]. This new lower bound combined with a careful “random restriction” procedure (that transforms general depth 4 homogeneous circuits to depth 4 circuits with bounded support) gives us our final result.
The full version of the paper is available on ECCC at http://eccc.hpi-web.de/report/2013/181/
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Agrawal, M., Vinay, V.: Arithmetic circuits: A chasm at depth four. In: Proceedings of the 49th Annual FOCS, pp. 67–75 (2008)
Chillara, S., Mukhopadhyay, P.: Depth-4 lower bounds, determinantal complexity: A unified approach. CoRR, abs/1308.1640v3 (2013)
Fournier, H., Limaye, N., Malod, G., Srinivasan, S.: Lower bounds for depth 4 formulas computing iterated matrix multiplication. In: STOC 2014 (to appear, 2014)
Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. In: Proceedings of CCC (2013)
Kayal, N.: An exponential lower bound for the sum of powers of bounded degree polynomials. ECCC 19, 81 (2012)
Kayal, N., Limaye, N., Saha, C., Srinivasan, S.: An exponential lower bound for homogeneous depth four arithmetic formulas. ECCC (2014)
Kayal, N., Saha, C., Saptharishi, R.: A super-polynomial lower bound for regular arithmetic formulas. ECCC 20, 91 (2013)
Koiran, P.: Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science 448, 56–65 (2012)
Kumar, M., Saraf, S.: The limits of depth reduction for arithmetic formulas: It’s all about the top fan-in. In: STOC 2014 (to appear, 2014)
Kumar, M., Saraf, S.: Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. ECCC (2013)
Kumar, M., Saraf, S.: On the power of homogeneous depth 4 arithmetic circuits. ECCC (2014)
Limaye, N., Saha, C., Srinivasan, S.: Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas. In: STOC 2014 (to appear, 2014)
Nisan, N., Wigderson, A.: Lower bounds on arithmetic circuits via partial derivatives. In: Proceedings of the 36th Annual FOCS, pp. 16–25 (1995)
Raz, R., Yehudayoff, A.: Lower bounds and separations for constant depth multilinear circuits. In: Conference on Computational Complexity, pp. 128–139 (June 2008)
Raz, R.: Elusive functions and lower bounds for arithmetic circuits. Theory of Computing 6(1), 135–177 (2010)
Tavenas, S.: Improved bounds for reduction to depth 4 and depth 3. In: Chatterjee, K., Sgall, J. (eds.) MFCS 2013. LNCS, vol. 8087, pp. 813–824. Springer, Heidelberg (2013)
Valiant, L.: Completeness classes in algebra. In: Proceedings of the 11th Annual STOC, STOC 1979, pp. 249–261. ACM, New York (1979)
Valiant, L., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM Journal of Computation 12(4), 641–644 (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kumar, M., Saraf, S. (2014). Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds) Automata, Languages, and Programming. ICALP 2014. Lecture Notes in Computer Science, vol 8572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-43948-7_62
Download citation
DOI: https://doi.org/10.1007/978-3-662-43948-7_62
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-43947-0
Online ISBN: 978-3-662-43948-7
eBook Packages: Computer ScienceComputer Science (R0)