__
TR00-044 | 26th June 2000 00:00
__

#### On the Distribution of the Number of Roots of Polynomials and Explicit Logspace Extractors

**Abstract:**
Weak designs were defined by Raz, Reingold and Vadhan (1999) and are

used in constructions of extractors. Roughly speaking, a weak design

is a collection of subsets satisfying some near-disjointness

properties. Constructions of weak designs with certain parameters are

given in [RRV99]. These constructions are explicit in the sense that

they require time and space polynomial in the number of subsets.

However, the constructions require time and space polynomial in the

number of subsets even when needed to output only one specific subset

out of the collection. Hence,the constructions are not explicit in a

stronger sense.

In this work we provide constructions of weak designs (with parameters

similar to the known ones) that can be carried out in space logarithmic

in the number of subsets. Moreover, our constructions are explicit even

in a stronger sense; given an index to a subset, we output the

specified subset in time and space polynomial in the size of the index.

Using our constructions, we obtain extractors similar to the RRV

extractors in terms of parameters and that can be evaluated in

logarithmic space.

Our main construction is algebraic. In order to prove the properties

of weak designs we prove some combinatorial-algebraic lemmas that may

be interesting in their own right. These lemmas regard the number of

roots of polynomials over finite fields. In particular, we prove that

the number of polynomials (over any finite field) with $k$ roots,

vanishes exponentially in $k$. In other words, we prove that the

number of roots of a random polynomial is not only bounded by its

degree (a well known fact), but furthermore, it is concentrated

exponentially around its expectation (which is 1).