Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

摘要

We show the following Reduction Lemma: any -biased sample space with respect to (Boolean) linear tests is also 2-biased with respect to any system of independent linear tests. Combining this result with the previous constructions of -biased sample space with respect to linear tests, we obtain the first efficient construction of discrepancy sets (i.e. two-sided pseudo-random sets) for Boolean affine spaces. We also give a different version of the powering construction of -biased sample spaces given by Alon et al in order to obtain k-wise -biased sample spaces with respect to any affine spaces. The second main contribution of this paper is a new direct connection between the efficient construction of pseudo-random (both two-sided and one-sided) sets for Boolean affine spaces and the explicit construction of Boolean functions having hard branching program complexity. In the case of 1-read branching programs (1-BrPr), this connection relies on a different interpretation of Simon and Szegedy's Theorem in terms of Boolean linear systems. Our constructions of non trivial (i.e. of cardinality Missing close brace) discrepancy sets for Boolean affine spaces of dimension greater than n2 yield a set of Boolean functions in PH having very hard 1-BrPr size. In particular, we obtain a Boolean function in Missing close brace having 1-BrPr size not smaller than 2n?4logn. This bound is tight and improves over the best previously known bound which was 2n?s where s=O(n23log13n) [SZ96]. For the more general case of non deterministic, syntactic k-read branching programs (k-BrPr), we introduce a new method to derive explicit, exponential lower bounds that envolves the efficient construction of hitting sets (i.e. one-sided pseudo-random sets) for affine spaces of dimension o(n2) . Using an ``orthogonal'' representation of small Boolean affine spaces and again the Reduction Lemma, we give the required construction of hitting sets thus obtaining an explicit Boolean function that belongs to PH and has k-BrPr size not smaller than 2n1?o(1) for any k=olognloglogn . This asymptotically improves the exponents of the previous known lower bounds given in [BRS93,J95,O93] for some range of k.