Revision #2 Authors: A. E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

Accepted on: 20th November 1998 00:00

Downloads: 2047

Keywords:

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 Authors: A. E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

Accepted on: 11th May 1998 00:00

Downloads: 1837

Keywords:

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

TR97-053 Authors: Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

Publication: 14th November 1997 17:10

Downloads: 1729

Keywords:

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