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

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 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: Markus Bläser, A - Lower Bound for the Rank of - Matrix Multiplication over Arbitrary Fields, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.45, October 17-18, 1999
• 4: Nader H. Bshouty, A lower bound for matrix multiplication, SIAM Journal on Computing, v.18 n.4, p.759-765, Aug. 1989 [doi>10.1137/0218052]
• 5: Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983 [doi>10.1145/800061.808731]
• 6: M.L.Furst,J.B.Sxe,ndM.Sipser.Prity,circuits, and the polynomial-time hierarchy.In FOCS pages 260 -270,1981.
• 7: Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science: vol. 3, 1988, Annual Reviews Inc., Palo Alto, CA, 1988
• 8: Dima Grigoriev , Marek Karpinski, An exponential lower bound for depth 3 arithmetic circuits, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.577-582, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276872]
• 9: D. Grigoriev , A. Razborov, Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.269, November 08-11, 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 Hastad, Almost optimal lower bounds for small depth circuits, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.6-20, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12132]
• 12: Russell Impagliazzo , Ramamohan Paturi , Michael E. Saks, Size--Depth Tradeoffs for Threshold Circuits, SIAM Journal on Computing, v.26 n.3, p.693-707, June 1997 [doi>10.1137/S0097539792282965]
• 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: Amir Shpilka , Avi Wigderson, Depth-3 Arithmetic Formulae over Fields of Characteristic Zero, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.87, May 04-06, 1999
• 16: R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
• 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: Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
  B.8 Performance and Reliability

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

General Terms:
Design, Performance, Theory, Verification