All reports by Author J. L. Baskakov:

__
TR97-053
| 10th November 1997
__

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim#### Small Random Sets for Affine Spaces and Better Explicit Lower Bounds for Branching Programs

Revisions: 2

Alexander E. Andreev, J. L. Baskakov, Andrea E. F. Clementi, Jose' D. P. Rolim

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

more >>>