research-article

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

Authors:

Srikanth SrinivasanAuthors Info & Claims

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Pages 119 - 127

https://doi.org/10.1145/2591796.2591823

Published: 31 May 2014 Publication History

Abstract

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMM_n,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size n^{Ω(log n}), if d = Ω (log² n). More-over, any depth-4 homogeneous formula computing the determinant polynomial Det_n -- the determinant of a generic n × n matrix -- has size n^{Ω(log n)}.

Supplementary Material

MP4 File (p119-sidebyside.mp4)

Download
173.63 MB

References

[1]

M. Agrawal, C. Saha, R. Saptharishi, and N. Saxena. Jacobian hits circuits: hitting-sets, lower bounds for depth-d occur-k formulas & depth-3 transcendence degree-k circuits. In STOC, pages 599--614, 2012.

Digital Library

[2]

M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, pages 67--75. IEEE Computer Society, 2008.

Digital Library

[3]

E. Allender, J. Jiao, M. Mahajan, and V. Vinay. Non-Commutative Arithmetic Circuits: Depth Reduction and Size Lower Bounds. Theor. Comput. Sci., 209(1-2):47--86, 1998.

Digital Library

[4]

H. Fournier, N. Limaye, G. Malod, and S. Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. Electronic Colloquium on Computational Complexity (ECCC), 20:100, 2013.

[5]

D. Grigoriev and M. Karpinski. An exponential lower bound for depth 3 arithmetic circuits. In STOC, pages 577--582, 1998.

Digital Library

[6]

D. Grigoriev and A. A. Razborov. Exponential complexity lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields. In FOCS, pages 269--278, 1998.

Digital Library

[7]

A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Approaching the chasm at depth four. In Proceedings of the Conference on Computational Complexity (CCC), 2013.

[8]

A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. Electronic Colloquium on Computational Complexity (ECCC), 20:26, 2013.

[9]

V. Guruswami. Introduction to coding theory, Lecture 2: Gilbert-Varshamov bound. http://www.cs.cmu.edu/venkatg/teaching/codingtheory/, 2010.

[10]

N. Kayal. An exponential lower bound for the sum of powers of bounded degree polynomials. Electronic Colloquium on Computational Complexity (ECCC), 19:81, 2012.

[11]

N. Kayal, N. Limaye, C. Saha, and S. Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. Electronic Colloquium on Computational Complexity (ECCC), 21:5, 2014.

[12]

N. Kayal, C. Saha, and R. Saptharishi. A super-polynomial lower bound for regular arithmetic formulas. Electronic Colloquium on Computational Complexity (ECCC), 20:91, 2013.

[13]

P. Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theor. Comput. Sci., 448:56--65, 2012.

Digital Library

[14]

M. Kumar and S. Saraf. The limits of depth reduction for arithmetic formulas: It's all about the top fan-in. Electronic Colloquium on Computational Complexity (ECCC), 20:153, 2013.

[15]

M. Kumar and S. Saraf. Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin. Electronic Colloquium on Computational Complexity (ECCC), 20:68, 2013.

[16]

M. Kumar and S. Saraf. Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits. CoRR, abs/1312.5978, 2013.

[17]

N. Nisan. Lower bounds for non-commutative computation (extended abstract). In STOC, pages 410--418, 1991.

Digital Library

[18]

N. Nisan and A. Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217--234, 1997.

Digital Library

[19]

R. Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121--135, 2006.

[20]

R. Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009.

Digital Library

[21]

R. Raz and A. Yehudayoff. Lower Bounds and Separations for Constant Depth Multilinear Circuits. Computational Complexity, 18(2):171--207, 2009.

[22]

A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207--388, 2010.

Digital Library

[23]

S. Skyum and L. G. Valiant. A Complexity Theory Based on Boolean Algebra. J. ACM, 32(2):484--502, 1985.

Digital Library

[24]

S. Tavenas. Improved bounds for reduction to depth 4 and depth 3. In MFCS, pages 813--824, 2013.

[25]

L. G. Valiant. Completeness Classes in Algebra. In STOC '79: Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 249--261, New York, NY, USA, 1979. ACM Press.

Digital Library

[26]

L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput., 12(4):641--644, 1983.

Cited By

Limaye NSrinivasan STavenas S(2022)Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00083(804-814)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00083
Chillara S(2021)On Computing Multilinear Polynomials Using Multi-r-ic Depth Four CircuitsACM Transactions on Computation Theory10.1145/346095213:3(1-21)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3460952
Ramya CRao B(2019)Lower bounds for Sum and Sum of Products of Read-once FormulasACM Transactions on Computation Theory10.1145/331323211:2(1-27)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3313232
Show More Cited By

Index Terms

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

Recommendations

Lower bounds for depth 4 formulas computing iterated matrix multiplication
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMM_n,d, has size n^Ω(√d) as long as d = n^O(1). This ...
A super-polynomial lower bound for regular arithmetic formulas
STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

We consider arithmetic formulas consisting of alternating layers of addition (+) and multiplication (×) gates such that the fanin of all the gates in any fixed layer is the same. Such a formula Φ which additionally has the property that its formal/...
Tensor-rank and lower bounds for arithmetic formulas
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

We show that any explicit example for a tensor A:[n]^r -> F with tensor-rank ≥ n^{r ⋅ (1- o(1))}, (where r ≤ log n / log log n), implies an explicit super-polynomial lower bound for the size of general arithmetic formulas over F. This shows that strong ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

May 2014

984 pages

ISBN:9781450327107

DOI:10.1145/2591796

Program Chair:
David Shmoys
Cornell University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '14

Sponsor:

SIGACT

STOC '14: Symposium on Theory of Computing

May 31 - June 3, 2014

New York, New York

Acceptance Rates

STOC '14 Paper Acceptance Rate 91 of 319 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
146
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Limaye NSrinivasan STavenas S(2022)Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00083(804-814)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00083
Chillara S(2021)On Computing Multilinear Polynomials Using Multi-r-ic Depth Four CircuitsACM Transactions on Computation Theory10.1145/346095213:3(1-21)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3460952
Ramya CRao B(2019)Lower bounds for Sum and Sum of Products of Read-once FormulasACM Transactions on Computation Theory10.1145/331323211:2(1-27)Online publication date: 2-Apr-2019
https://dl.acm.org/doi/10.1145/3313232
Kayal NSaha C(2016)Lower Bounds for Depth-Three Arithmetic Circuits with small bottom faninComputational Complexity10.1007/s00037-016-0132-025:2(419-454)Online publication date: 1-Jun-2016
https://dl.acm.org/doi/10.1007/s00037-016-0132-0
Bera SChakrabarti AZuckerman D(2015)A depth-five lower bound for iterated matrix multiplicationProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833236(183-197)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833236
Kayal NSaha CZuckerman D(2015)Lower bounds for depth three arithmetic circuits with small bottom faninProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833235(158-182)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833235
Forbes M(2015)Deterministic Divisibility Testing via Shifted Partial DerivativesProceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2015.35(451-465)Online publication date: 17-Oct-2015
https://dl.acm.org/doi/10.1109/FOCS.2015.35
Fournier HLimaye NMahajan MSrinivasan S(2015)The Shifted Partial Derivative Complexity of Elementary Symmetric PolynomialsMathematical Foundations of Computer Science 201510.1007/978-3-662-48054-0_27(324-335)Online publication date: 11-Aug-2015
https://doi.org/10.1007/978-3-662-48054-0_27

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents