Chockler, Hana; Zwick, Uri Which bases admit non-trivial shrinkage of formulae? (English) Zbl 0988.06009 Comput. Complexity 10, No. 1, 28-40 (2001). Summary: 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 unate, i.e., monotone increasing or decreasing in each of their variables. As a consequence, we get nonlinear lower bounds on the formula complexity of the parity function over any basis composed only of unate functions. Cited in 2 Documents MSC: 06E30 Boolean functions 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 03D15 Complexity of computation (including implicit computational complexity) 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) Keywords:shrinkage exponent; random restrictions; Boolean functions; nonlinear lower bounds; formula complexity; parity function PDFBibTeX XMLCite \textit{H. Chockler} and \textit{U. Zwick}, Comput. Complexity 10, No. 1, 28--40 (2001; Zbl 0988.06009) Full Text: DOI