OPTIMAL BOUNDS FOR THE APPROXIMATION OF BOOLEAN FUNCTIONS AND SOME APPLICATIONS

This paper presents an optimal bound on the Shannon function L(n, m, e psilon) that gives the worst-case circuit-size complexity to approxima te, within an approximation degree at least epsilon, partial boolean f unctions having n inputs and domain size m. That is L(n,m,epsilon) = T heta(m epsilon(2)/log(2 + m epsilon(2))) + O(n). Our bound applies to any partial boolean function and any approximation degree, and thus co mpletes the study of boolean function approximation introduced by Pipp enger (1977). Our results give an upper bound for the hardness functio n h(f), introduced by Nisan and Wigderson (1994), which denotes the mi nimum value l for which there exists a circuit of size at most I that approximates a boolean function f with degree at least 1/l. Indeed, if H(n) denotes the maximum hardness value achieved by boolean functions with n inputs, we prove that for almost every n H(n) less than or equ al to 2(n/3) + n(2) + O(1). The exponent n/3 in the above inequality i mplies that no family of boolean functions exists which has 'full' har dness. This fact establishes connections with Allender and Strauss' (1 994) work that explores the structure of BPP. Finally, we show that fo r almost every n and for almost every boolean function f of n inputs w e have h(f) greater than or equal to 2(n/3-2logn). The contribution in the proof of the upper bound for L(n, m, epsilon) can be viewed as a set of technical results that globally show how boolean linear operato rs are 'well' distributed on the class of 4-regular domains. This prop erty is then applied to approximate partial boolean functions on gener al domains using a suitable composition of boolean linear operators.