Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR97-053 | 20th November 1998 00:00

#### Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs Revision of: TR97-053

Revision #2
Authors: A. E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim
Accepted on: 20th November 1998 00:00
Keywords:

Abstract:

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$.

Revision #1 to TR97-053 | 11th May 1998 00:00

#### Small Pseudo-Random Sets Yield Hard Functions: New Tight Explicit Lower Bounds for Branching Programs Revision of: TR97-053

Revision #1
Authors: A. E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim
Accepted on: 11th May 1998 00:00
Keywords:

Abstract:

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$.

### Paper:

TR97-053 | 10th November 1997 00:00

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

TR97-053
Authors: Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim
Publication: 14th November 1997 17:10
Keywords:

Abstract:

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$.

ISSN 1433-8092 | Imprint