On the complexity of balanced Boolean functions
This paper introduces the notions of balanced and strongly balanced Boolean functions and examines the complexity of these functions using harmonic analysis on the hypercube. The results are applied to derive a lower bound related to AC(0) functions. (C) 1999 Elsevier Science B.V. All rights reserved.
balanced boolean functions strongly balanced boolean functions harmonic analysis spectral characterization computational complexity