Circuit bottom fan-in and computational power Conference Paper uri icon

abstract

  • 1997 IEEE. We investigate the relationship between circuit bottom fan-in and circuit size when circuit depth is fixed. We show that in order to compute certain functions, a moderate reduction in circuit bottom fan-in will cause significant increase in circuit size. In particular, we prove that there are functions that are computable by circuits of linear size and depth k with bottom fan-in 2 but require exponential size for circuits of depth k with bottom fan-in 1. A general scheme is established to study the trade-off between circuit bottom fan-in and circuit size. Based on this scheme, we are able to prove, for example, that for any integer c, there are functions that are computable by circuits of linear size and depth k with bottom fan-in O(log n) but require exponential size for circuits of depth k with bottom fan-in c, and that for any constant >0, there are functions that are computable by circuits of linear size and depth k with bottom fan-in log n but require superpolynomial size for circuits of depth k with bottom fan-in O(log/sup 1-/n). A consequence of these results is that the three input read-modes of alternating Turing machines proposed in the literature are all distinct.

name of conference

  • Proceedings of Computational Complexity. Twelfth Annual IEEE Conference

published proceedings

  • 2013 IEEE Conference on Computational Complexity

author list (cited authors)

  • Cai, L., Chen, J., & Hastad, J.

citation count

  • 1

complete list of authors

  • Cai, Liming||Chen, Jianer||Hastad, J

publication date

  • January 1997