__
TR05-155 | 10th December 2005 00:00
__

#### Constructions of low-degree and error-correcting epsilon-biased sets

**Abstract:**
In this work we give two new constructions of $\epsilon$-biased

generators. Our first construction answers an open question of

Dodis and Smith, and our second construction

significantly extends a result of Mossel et al.

In particular we obtain the following results:

1. We construct a family of asymptotically good binary codes

such that the codes in our family are also epsilon-biased sets

for an exponentially small epsilon. Our encoding and decoding

algorithms run in polynomial time in the block length of the code.

This answers an open question of Dodis and Smith.

2. We construct a degree k epsilon-biased generator,

G:{0,1}^m \to {0,1}^n, for every k=o(\log n). For k constant we

get that n=\Omega(m/log(1/\epsilon))^k, which is nearly optimal.

Our result also separates degree $k$ generators from generators in

NC_k^0, showing that the stretch of the former can be

much larger than the stretch of the latter. This problem of

constructing degree $k$ generators was introduced by Mossel et

al. who gave a construction only for the case of

degree 2 generators.