ECCC-Report TR05-155https://eccc.weizmann.ac.il/report/2005/155Comments and Revisions published for TR05-155en-usWed, 14 Dec 2005 09:31:00 +0200
Paper TR05-155
| Constructions of low-degree and error-correcting epsilon-biased sets |
Amir Shpilka
https://eccc.weizmann.ac.il/report/2005/155In 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.
Wed, 14 Dec 2005 09:31:00 +0200https://eccc.weizmann.ac.il/report/2005/155