Almost k-Wise independence and hard Boolean functions

Valentine Kabanets

---

Abstract

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(log n)}, and a function in LINSPACE with the lower bound 2^{n-log n-O(1)}. Our constructions are simpler than those of Andreev et al., 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⁰[2] (computable by a depth 3, polynomial-size circuit over the basis {∧,⊕,1}) with the optimal lower bound 2^{n-log n-O(1)} for 1-b.p.'s.

---

Versions

• journal version in Theoretical Computer Science, 297(1-3), pages 281-295, 2003.
• extended abstract in Proceedings of the Fourth Latin American Symposium on Theoretical Informatics (LATIN'00), Lecture Notes in Computer Science, Volume 1776, pages 197-206, 2000.

---