TY - GEN

T1 - Size-depth trade-offs for threshold circuits

AU - Impagliazzo, Russell

AU - Paturi, Ramamohan

AU - Saks, Michael E.

N1 - Funding Information:
lDepartment of Computer Science and Engineering, versity of California, San Diego, La Jolla, Ca 92093 tDept. of Mathematics, Rutgers University, New Brunswick, NJ 08903 and Dept. of Computer Science and Engineering, UCSD, La Jolla, Ca. 92093. Research supported in part by NSF grant CCR-8911388 and AFOSR grants 89-0512 and 90-0008.
Publisher Copyright:
© 1993 ACM.

PY - 1993/6/1

Y1 - 1993/6/1

N2 - The following size-depth trade- off for threshold circuits is obtained: Any threshold circuit of depth d that computes the parity function on n variables must have at least n1+cθ-d edges, where constants c > 0 and θ < 3 are constants independent of n and d. Previously known constructions show that up to the choice of c and θ this bound is best possible. In particular, the lower bound implies an affirmative answer to the conjecture of Paturi and Saks that a bounded depth threshold circuit that computes parity requires a super-linear number of edges. This is the first super-linear lower bound for an explicit function that holds for any fixed depth, and the first that applies to threshold circuits with unrestricted weights. The trade-off is obtained as a consequence of a general restriction theorem for threshold circuits with a small number of edges: For any threshold circuit with n inputs, depth d and at most len edges, there exists a partial assignment to the inputs that fixes the output of the circuit to a constant, while leaving [n/(c1k)C2θd J variables unfixed, where ci,c2 > 0 and 0 < 3 are constants independent of n,k, and d. A trade-off between the number of gates and depth is also proved: Any threshold circuit of depth d that computes the parity of n variables has at least (n/2)1/2(d-1)) gates. This trade-off, which is essentially the best possible, was proved previously (with a better constant) for the case of threshold circuits with polynomially bounded weights in (22); the result in the present paper holds for unrestricted weights.

AB - The following size-depth trade- off for threshold circuits is obtained: Any threshold circuit of depth d that computes the parity function on n variables must have at least n1+cθ-d edges, where constants c > 0 and θ < 3 are constants independent of n and d. Previously known constructions show that up to the choice of c and θ this bound is best possible. In particular, the lower bound implies an affirmative answer to the conjecture of Paturi and Saks that a bounded depth threshold circuit that computes parity requires a super-linear number of edges. This is the first super-linear lower bound for an explicit function that holds for any fixed depth, and the first that applies to threshold circuits with unrestricted weights. The trade-off is obtained as a consequence of a general restriction theorem for threshold circuits with a small number of edges: For any threshold circuit with n inputs, depth d and at most len edges, there exists a partial assignment to the inputs that fixes the output of the circuit to a constant, while leaving [n/(c1k)C2θd J variables unfixed, where ci,c2 > 0 and 0 < 3 are constants independent of n,k, and d. A trade-off between the number of gates and depth is also proved: Any threshold circuit of depth d that computes the parity of n variables has at least (n/2)1/2(d-1)) gates. This trade-off, which is essentially the best possible, was proved previously (with a better constant) for the case of threshold circuits with polynomially bounded weights in (22); the result in the present paper holds for unrestricted weights.

UR - http://www.scopus.com/inward/record.url?scp=0027235221&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027235221&partnerID=8YFLogxK

U2 - 10.1145/167088.167233

DO - 10.1145/167088.167233

M3 - Conference contribution

AN - SCOPUS:0027235221

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 541

EP - 550

BT - Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993

PB - Association for Computing Machinery

T2 - 25th Annual ACM Symposium on Theory of Computing, STOC 1993

Y2 - 16 May 1993 through 18 May 1993

ER -