Article

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

Authors:

Amir ShpilkaAuthors Info & Claims

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

Pages 409 - 418

https://doi.org/10.1145/380752.380833

Published: 06 July 2001 Publication History

Abstract

We prove super-linear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth Boolean circuits with arbitrary gates. The bounds apply for several explicit functions, and, most importantly, for matrix product. In particular, we obtain the following results:

We show that the number of edges in any constant depth arithmetic circuit for matrix product (over any field is super-linear in m^2 (where m \times m is the size of each matrix). That is, the lower bound is super-linear in the number of input variables. Moreover, if the circuit is bilinear the result applies also for the case where the circuit gets for free any product of two linear functions.

We show that the number of edges in any constant depth arithmetic circuit for the trace of the product of 3 matrices (over fields with characteristic~0) is super-linear in m^2. (Note that the trace is a single-output function).

We give explicit examples for n Boolean functions f_1,\dots,f_ , such that any constant depth Boolean circuit with arbitrary gates for f_1,...,f_n has a super-linear number of edges. The lower bound is proved also for circuits with arbitrary gates over any finite field. The bound applies for matrix product over finite fields as well as for several other explicit functions.

References

[1]

M.Ajti.S11 -formul e on .nite structures.Annals of Pure and Applied Logic 1983.

[2]

W.B ur nd V.Strassen.The complexity of p rti l deriv tives.Theoretical Computer Science 22:317 -330, 1983.

[3]

M.Blaser.A 52 lower bound for the rank of non matrix multiplication over rbitrary .elds.In FOCS pages 45-50,1999.

[4]

N.H.Bshouty.A lower bound for matrix multiplication.SIAM Journal on Computing 18:759 -765,1989.

[5]

D.Dolev,C.Dwork,N.J.Pippenger,nd A.Wigderson.Superconcentrators,generalizer and generalized connectors.In STOC pages 42 -51,1983.

[6]

M.L.Furst,J.B.Sxe,ndM.Sipser.Prity,circuits, and the polynomial-time hierarchy.In FOCS pages 260 -270,1981.

[7]

J.v.z.G then.Algebraic complexity theory.Ann. Rev. Computer Science pages 317 -347,1988.

[8]

D.Grigoriev nd M.K rpinski.An exponential lower bound for depth 3 rithmetic circuits.In STOC pages 577 -582,1998.

[9]

D.Grigoriev nd A.A.R zborov.Exponential complexity lower bounds for depth 3 rithmetic circuits in algebras of functions over .nite .elds.In FOCS pages 269 -278,1998.

[10]

A.H jnal,W.Maass,P.Pudlak,M.Szegedy,nd G.Turan.Threshold circuits of bounded depth.In FOCS pages 99 -110,1987.

[11]

J.Hostad.Almost optimal lower bounds for small depth circuits.In STOC pages 6 -20,1986.

[12]

R.Impagliazzo,R.Paturi,and M.Saks.Size-depth trade-o .s for threshold circuits.SIAM Journal on Computing 26:693 -707,1997.

[13]

P.Pudl k.Communic tion in bounded depth circuits. Combinatorica 14(2):203 -216,1994.

[14]

A.A.Razborov.Lower bounds for the size of circuits with bounded depth with basis {., .}.Mat. Zametki 1987.

[15]

A.Shpilk nd A.Wigderson.Depth-3 rithmetic formul e over .elds of characteristic zero.In CCC volume 14,pages 87 -96,1999.

Digital Library

[16]

R.Smolensky.Algebraic methods in the theory of lower bounds for Boole n circuit complexity.In STOC pages 77 -82,1987.

[17]

V.Strassen.Gaussian elimination is not optimal. Numer. Math 13:354 -356,1969.

[18]

V.Strassen.Die berechnungskomplexiat von elementarsymmetrischen funktionen und von interpolationskoe .zienten.Numer. Math 20:238 -251, 1973.

[19]

L.G.V liant.Graph-theoretic rguments in low-level complexity.In Lecture notes in Computer Science volume 53,pages 162 -176.1977.

[20]

A.C.Yao.Sep rating the polynomial hierarchy by oracles.In FOCS pages 1 -10,1985.

Cited By

Shpilka A(2019)Affine projections of symmetric polynomialsJournal of Computer and System Sciences10.1016/S0022-0000(02)00021-165:4(639-659)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/S0022-0000%2802%2900021-1
Dvir ZShpilka AGabow HFagin R(2005)Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuitsProceedings of the thirty-seventh annual ACM symposium on Theory of computing10.1145/1060590.1060678(592-601)Online publication date: 22-May-2005
https://dl.acm.org/doi/10.1145/1060590.1060678
Raz RReif J(2002)On the complexity of matrix productProceedings of the thiry-fourth annual ACM symposium on Theory of computing10.1145/509907.509932(144-151)Online publication date: 19-May-2002
https://dl.acm.org/doi/10.1145/509907.509932
Show More Cited By

Index Terms

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates
1. Hardware
  1. Integrated circuits
    1. Logic circuits
  2. Robustness
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Paths and connectivity problems
  2. Mathematical analysis
    1. Numerical analysis
      1. Computations on matrices

Recommendations

Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates

We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth ...
Lower bounds for depth-2 and depth-3 Boolean circuits with arbitrary gates
CSR'08: Proceedings of the 3rd international conference on Computer science: theory and applications

We consider depth-2 and 3 circuits over the basis consisting of all Boolean functions. For depth-3 circuits, we prove a lower bound Ω(n log n) for the size of any circuit computing the cyclic convolution. For depth-2 circuits, a lower bound Ω(n^3/2) for ...
Exponential lower bound for bounded depth circuits with few threshold gates

We prove an exponential lower bound on the size of bounded depth circuits with O(logn) threshold gates computing an explicit function (namely, the parity function). Previously exponential lower bounds were known only for circuits with one threshold ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '01: Proceedings of the thirty-third annual ACM symposium on Theory of computing

July 2001

755 pages

ISBN:1581133499

DOI:10.1145/380752

Copyright © 2001 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: 06 July 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC01

Sponsor:

SIGACT

STOC01: 33rd ACM Symposium on Theory of Computing

Hersonissos, Greece

Acceptance Rates

STOC '01 Paper Acceptance Rate 83 of 230 submissions, 36%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
34
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Shpilka A(2019)Affine projections of symmetric polynomialsJournal of Computer and System Sciences10.1016/S0022-0000(02)00021-165:4(639-659)Online publication date: 1-Jan-2019
https://dl.acm.org/doi/10.1016/S0022-0000%2802%2900021-1
Dvir ZShpilka AGabow HFagin R(2005)Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuitsProceedings of the thirty-seventh annual ACM symposium on Theory of computing10.1145/1060590.1060678(592-601)Online publication date: 22-May-2005
https://dl.acm.org/doi/10.1145/1060590.1060678
Raz RReif J(2002)On the complexity of matrix productProceedings of the thiry-fourth annual ACM symposium on Theory of computing10.1145/509907.509932(144-151)Online publication date: 19-May-2002
https://dl.acm.org/doi/10.1145/509907.509932
Shpilka A(2001)Lower bounds for matrix productProceedings 42nd IEEE Symposium on Foundations of Computer Science10.1109/SFCS.2001.959910(358-367)Online publication date: 2001
https://doi.org/10.1109/SFCS.2001.959910
Shpilka A(2000)Affine projections of symmetric polynomialsProceedings 16th Annual IEEE Conference on Computational Complexity10.1109/CCC.2001.933883(160-171)Online publication date: 2000
https://doi.org/10.1109/CCC.2001.933883

View Options

Get Access

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