文章基本信息

标题：Almost k-Wise Independence and Boolean Functions Hard for Read-Once Branching Programs
本地全文：下载
作者：Valentine Kabanets
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1999
卷号：1999
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：almost k-wise independence, derandomization, exponential lowerbounds for read-once branching programs, r-mixed Boolean functions