ECCC-Report TR99-004https://eccc.weizmann.ac.il/report/1999/004Comments and Revisions published for TR99-004en-usSat, 06 Nov 1999 00:00:00 +0200
Revision 1
| Almost k-Wise Independence and Hard Boolean Functions Revision of: TR99-004 |
Valentine Kabanets
https://eccc.weizmann.ac.il/report/1999/004#revision1Andreev 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.
Sat, 06 Nov 1999 00:00:00 +0200https://eccc.weizmann.ac.il/report/1999/004#revision1
Paper TR99-004
| Almost $k$-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs |
Valentine Kabanets
https://eccc.weizmann.ac.il/report/1999/004Andreev 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.
Tue, 23 Feb 1999 11:08:42 +0200https://eccc.weizmann.ac.il/report/1999/004