Abstract
We introduce the polynomial coefficient matrix and identify maximum rank of this matrix under variable substitution as a complexity measure for multivariate polynomials. We use our techniques to prove super-polynomial lower bounds against several classes of non-multilinear arithmetic circuits. In particular, we obtain the following results :
-
As our first main result, we prove that any homogeneous depth-3 circuit for computing the product of d matrices of dimension n ×n requires Ω(n d − 1/2d) size. This improves the lower bounds in [9] for d = ω(1).
-
As our second main result, we show that there is an explicit polynomial on n variables and degree at most \(\frac{n}{2}\) for which any depth-3 circuit C of product dimension at most \(\frac{n}{10}\) (dimension of the space of affine forms feeding into each product gate) requires size 2Ω(n). This generalizes the lower bounds against diagonal circuits proved in [14]. Diagonal circuits are of product dimension 1.
-
We prove a n Ω(logn) lower bound on the size of product-sparse formulas. By definition, any multilinear formula is a product-sparse formula. Thus, this result extends the known super-polynomial lower bounds on the size of multilinear formulas [11].
-
We prove a 2Ω(n) lower bound on the size of partitioned arithmetic branching programs. This result extends the known exponential lower bound on the size of ordered arithmetic branching programs [7].
The full version of the paper is available as a technical report at the ECCC. Technical report No. ECCC-TR-13-028. See http://eccc.hpi-web.de/report/2013/028/
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Arithmetic Circuit
- Partial Derivative Matrix
- Multilinear Polynomial
- Multilinear Formula
- Multilinear Circuit
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., Saha, C., Saptharishi, R., Saxena, N.: Jacobian Hits Circuits: Hitting-sets, Lower Bounds for Depth-d Occur-k Formulas & Depth-3 Transcendence Degree-k Circuits. In: Proceedings of ACM Symposium on Theory of Computing (STOC), pp. 599–614 (2012)
Agrawal, M., Vinay, V.: Arithmetic Circuits: A Chasm at Depth Four. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 67–75 (2008)
Dvir, Z., Malod, G., Perifel, S., Yehudayoff, A.: Separating Multilinear Branching Programs and Formulas. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 615–624 (2012)
Grigoriev, D., Razborov, A.: Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 269–278 (1998)
Grigoriev, D., Karpinski, M.: An Exponential Lower Bound for Depth 3 Arithmetic Circuits. In: Proceedings of Symposium on Theory of Computing (STOC), pp. 577–582 (1998)
Gupta, A., Kamath, P., Kayal, N., Saptharishi, R.: Approaching the chasm at depth four. To Appear in Conference on Computational Complexity (2013)
Jansen, M.J.: Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. In: Ochmański, E., Tyszkiewicz, J. (eds.) MFCS 2008. LNCS, vol. 5162, pp. 407–418. Springer, Heidelberg (2008)
Koiran, P.: Arithmetic Circuits: The Chasm at Depth Four Gets Wider. Theor. Comput. Sci. 448, 56–65 (2012)
Nisan, N., Wigderson, A.: Lower Bounds on Arithmetic Circuits via Partial Derivatives. In: Proceedings of Symposium on Foundations of Computer Science (FOCS), pp. 16–25 (1995)
Raz, R., Yehudayoff, A.: Lower Bounds and Separations for Constant Depth Multilinear Circuits. In: Proceedings of Conference on Computational Complexity, pp. 128–139 (June 2008)
Raz, R.: Separation of Multilinear Circuit and Formula Size. Theory of Computing 2(1), 121–135 (2006)
Raz, R.: Multi-linear Formulas for Permanent and Determinant are of Super-polynomial Size. Journal of ACM 56, 8:1–8:17 (2009)
Raz, R., Shpilka, A., Yehudayoff, A.: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. SIAM Journal of Computing 38(4), 1624–1647 (2008)
Saxena, N.: Diagonal Circuit Identity Testing and Lower Bounds. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 60–71. Springer, Heidelberg (2008)
Shpilka, A.: Affine Projections of Symmetric Polynomials. In: Proceedings of Conference on Computational Complexity, pp. 160–171 (2001)
Shpilka, A., Wigderson, A.: Depth-3 Arithmetic Circuits over Fields of Characteristic Zero. Computational Complexity 10(1), 1–27 (2001)
Shpilka, A., Yehudayoff, A.: Arithmetic Circuits: A Survey of Recent Results and Open Questions. Foundations and Trends in Theoretical Computer Science 5(3-4), 207–388 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kumar, M., Maheshwari, G., Sarma M.N., J. (2013). Arithmetic Circuit Lower Bounds via MaxRank. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds) Automata, Languages, and Programming. ICALP 2013. Lecture Notes in Computer Science, vol 7965. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39206-1_56
Download citation
DOI: https://doi.org/10.1007/978-3-642-39206-1_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39205-4
Online ISBN: 978-3-642-39206-1
eBook Packages: Computer ScienceComputer Science (R0)