Linear lower bounds on unbounded fan-in Boolean circuits (Q1068792)

A computing model called CA-circuit is introduced as a generalisation of the unbounded fan-in Boolean circuit. Defining the communication complexity of CA-circuits a method for proving lower bounds on the number of gates in CA-circuits is obtained. The use of the method is presented to establish linear lower bounds for specific Boolean functions. It is proved that the communication complexity of CA-circuits is a special case of the communication complexity for VLSI, i.e. that the communication complexity of VLSI circuits provides lower bounds on the communication complexity of CA-circuits. A Boolean function with zero VLSI communication complexity and linear CA-circuit communication complexity is shown.