Almost k-wise independence and hard Boolean functions
We construct Boolean functions (computable by polynomial-size circuits) with large lower bounds for read-once branching program (1-b.p.'s): a function in P with the lower bound 2(n-polylog(n)), a function in quasipolynomial time with the lower bound 2(n-O(logn)), and a function in LINSPACE with the lower bound 2(n-logn-O(1)). Our constructions are simpler than those of Andreev et al. (Electronic Colloq. on Computational Complexity, TR97-053, 1997), as we apply the idea of almost k-wise independence more directly, without the use of discrepancy set generators for large affine subspaces. The simplicity of our constructions also allows us to observe that there exists a Boolean function in AC(0)[2] (computable by a depth 3, polynomial-size circuit over the basis {boolean AND, circle plus, 1}) with the optimal lower bound 2(n-logn-O(1)) for 1-b.p.'s. (C) 2002 Elsevier Science B.V. All rights reserved.
almost k-wise independence derandomization exponential lower bounds for read-once branching programs r-mixed boolean functions