Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-155 | 10th December 2005 00:00

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


Authors: Amir Shpilka
Publication: 14th December 2005 09:31
Downloads: 1832


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.

ISSN 1433-8092 | Imprint