Lower Bounds for the Complexity of Restrictions of Boolean Functions

The complexity of restrictions of Boolean functions is studied in various computational models. Lower bounds for the complexity of the most complicated restrictions to domains of fixed size are established. The complexity bounds are shown to be tight up to a constant multiplicative factor in the case of logic circuits. For every Boolean function of variables whose circuit size is greater than , where is an arbitrary positive constant, it is proved that there exists a domain in {0, 1} the restriction to which has a nonlinear circuit size that differs by a constant factor from the circuit size of the most complicated partial Boolean function defined on this domain. Any Boolean function of variables is proved to be uniquely determined by its values in no more than domains whose sizes are bounded from above by the product of the function complexity and .