Estimates of Information Cost of Computing Boolean Functions in Combination Circuits

A new measure of the complexity of Boolean functions is introduced, this being defined by the quantity of information transmitted over all the channels of a circuit that computes a Boolean vector-valued function. Upper and lower bounds for this complexity measure are obtained.