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

R. Raz, A. Shpilka

Research output: Contribution to journalConference article

12 Scopus citations

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: 1. We show that the number of edges in any constant depth arithmetic circuit for matrix product (over any field) is super-linear in m2 (where m × 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. 2. 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 m2. (Note that the trace is a single-output function). 3. We give explicit examples for n Boolean functions f1, ..., fn, such that any constant depth Boolean circuit with arbitrary gates for f1, ..., fn 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.

Original languageEnglish (US)
Pages (from-to)409-418
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2001
Externally publishedYes
Event33rd Annual ACM Symposium on Theory of Computing - Creta, Greece
Duration: Jul 6 2001Jul 8 2001

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Lower bounds for matrix product, in bounded depth circuits with arbitrary gates'. Together they form a unique fingerprint.

  • Cite this