__
Revision #1 to TR99-004 | 6th November 1999 00:00
__
#### Almost k-Wise Independence and Hard Boolean Functions Revision of: TR99-004

**Abstract:**
Andreev et al.~\cite{ABCR97} gave constructions of 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(\log n)}, and a function in LINSPACE with the lower bound

2^{n-\log n -O(1)}. We point out alternative, much simpler constructions

of such Boolean functions by applying the idea of almost k-wise

independence more directly, without the use of discrepancy set generators

for large affine subspaces; our constructions are obtained by

derandomizing the probabilistic proofs of existence of the corresponding

combinatorial objects. The simplicity of our new 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

{\wedge,\oplus,1}) with the optimal lower bound 2^{n-\log n -O(1)} for

1-b.p.'s.

__
TR99-004 | 3rd February 1999 00:00
__

#### Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs

**Abstract:**
Andreev et al.~\cite{ABCR97} give constructions of Boolean

functions (computable by polynomial-size circuits) that require large

read-once branching program (1-b.p.'s): a function in P that requires

1-b.p. of size at least $2^{n-\polylog(n)}$, a function in quasipolynomial

time that requires 1-b.p. of size at least $2^{n-O(\log n)}$, and a

function in LINSPACE that requires 1-b.p. of size $2^{n-\log n -O(1)}$. We

point out alternative, much simpler constructions of such Boolean

functions by applying the idea of almost $k$-wise independence more

directly, without the use of discrepancy set generators for large affine

subspaces. Our constructions are obtained by derandomizing the

probabilistic proofs of existence of the corresponding combinatorial

objects.