In several previous works
the explicit construction of a computationally-hard function
with respect to a certain class of algorithms or Boolean circuits
has been used to derive small pseudo-random spaces. In this
paper, we revert this connection by presenting
two new direct relations
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 {\em branching program} complexity.

In the case of 1-read branching programs ($1$-$Br.Pr.$), we show that
the construction of non trivial (i.e. of cardinality $2^{o(n)}$) {\em
discrepancy sets} (i.e. two-sided pseudo-random sets)
for Boolean affine spaces of dimension greater
than $n/2$ yield a set of explicit Boolean functions
having very hard $1$-$Br.Pr.$ size. Then, by combining
the previous constructions of $\epsilon$-biased sample spaces for linear
tests and a simple ``Reduction'' Lemma, we derive
the required discrepancy set and obtain
a Boolean function in $\p$ having $1$-$Br.Pr.$ size not smaller
than $2^{n-O(\log^2 n)}$ and
a Boolean function in $\dtime(2^{O(\log^2n)})$ having
$1$-$Br.Pr.$ size not smaller
than $2^{n-O(\log n)}$. The latter bound is optimal and
both of them are exponential improvements over the
best previously known lower bound
that was $2^{n-3n^{1/2}}$~\cite{SZ98}.

As for the more general case of non deterministic, syntactic $k$-read
branching programs ($k$-$Br.Pr.$), we introduce a new method to derive
explicit, exponential
lower bounds that involves the efficient construction of {\em hitting
sets}
(i.e. one-sided pseudo-random sets) for affine spaces of dimension
$o(n/2)$. Using an appropriate
``orthogonal'' representation of small
Boolean affine spaces, we provide these
hitting sets thus obtaining an explicit Boolean function in $\p$ that
has $k$-$Br.Pr.$ size not smaller than $2^{n^{1-o(1)}}$
for {\em any} $k=o\left(\frac{\log n}{\log\log n}\right)$.
This improves the previous known lower bounds
given in~\cite{BRS93,J95,O93} for some range of $k$.

In several previous works the explicit construction of a
computationally-hard function with respect to a certain class of
algorithms or Boolean circuits has been used to derive small
pseudo-random spaces. In this paper, we revert this connection by
presenting two new direct relations 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$-$Br.Pr.$), we show that
the construction of non trivial (i.e. of cardinality $2^{o(n)}$)
discrepancy sets (i.e. two-sided pseudo-random sets) for Boolean affine
spaces of dimension greater than $n/2$ yield a set of explicit
Boolean functions having very hard $1$-$Br.Pr.$ size. Then, by
combining the previous constructions of $\epsilon$-biased sample
spaces for linear tests and a simple ``Reduction'' Lemma, we derive
the required discrepancy set and obtain a Boolean function in $\p$
having $1$-$Br.Pr.$ size not smaller than $2^{n-O(\log^2 n)}$ and
a Boolean function in ${\dtime(2^{O(\log^2n)})}^{\np}$ having
$1$-$Br.Pr.$ size not smaller than $2^{n-\log 4n}$. These bounds
improve over the best previously known lower bound
that was $2^{n-3n^{1/2}}$ [SZ98].

As for the more general case of non deterministic, syntactic $k$-read
branching programs ($k$-$Br.Pr.$), we introduce a new method to derive
explicit, exponential lower bounds that involves the efficient
construction of hitting sets (i.e. one-sided pseudo-random sets) for
affine spaces of dimension $o(n/2)$. Using an appropriate
``orthogonal'' representation of small Boolean affine spaces, we provide
these hitting sets thus obtaining an explicit Boolean function in $\p$
that has $k$-$Br.Pr.$ size not smaller than $2^{n^{1-o(1)}}$
for any $k=o\left(\frac{\log n}{\log\log n}\right)$.
This improves the previous known lower bounds
given in [BRS93,J95,O93] for some range of $k$.

We show the following Reduction Lemma: any
$\epsilon$-biased sample space with respect to (Boolean) linear
tests is also $2\epsilon$-biased with respect to
any system of independent linear tests. Combining this result with
the previous constructions of $\epsilon$-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 $\epsilon$-biased sample spaces given by Alon et al in
order to obtain $k$-wise $\epsilon$-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$-$Br.Pr.$),
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 $2^{o(n)$)
discrepancy sets for Boolean affine spaces of dimension greater
than $n/2$ yield a set of Boolean functions in $\PH$ having very
hard $1$-$Br.Pr.$ size. In particular, we obtain
a Boolean function in $\np^{\np \cap
\ppoly$ having $1$-$Br.Pr.$ size not smaller
than $2^{n-4\log n}$. This bound is tight and improves over
the best previously known bound which was $2^{n-s}$ where
$s=O(n^{2/3}\log^{1/3}n)$ [SZ96].

For the more general case of non deterministic, syntactic $k$-read
branching programs ($k$-$Br.Pr.$), 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(n/2)$ . 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$-$Br.Pr.$ size not smaller than $2^{n^{1-o(1)}}$
for any $k=o\left(\frac{\log n}{\log\log n}\right)$.
This asymptotically improves the exponents of the previous
known lower bounds
given in [BRS93,J95,O93] for some range of $k$.