Which formulae shrink under random restrictions
Hana Chockler, Uri Zwick · Research Portal (King's College London) · 2001
We show that the shrinkage exponent, under random restrictions, of formulae over a finite complete basis B of Boolean functions is strictly greater than 1 if and only if all the functions in B are monotone increasing or monotone decreasing in each one of their variables. As a consequence, we get non-linear lower bounds on the formula complexity of the parity function over any basis composed only of monotone increasing or decreasing functions.