Constructions of Low-Degree and Error-Correcting \in-Biased Generators
Amir Shpilka · 2006
In this work we give two new constructions of epsi-biased generators. Our first construction answers an open question of Dodis and Smith (2005), and our second construction significantly extends a result of Mossel et al. (2003). 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 epsi-biased sets for an exponentially small epsi. 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 (2005). (2) For every k = o(log n) we construct a degree k epsi-biased generator G:{0, 1}mrarr {0,1}n(namely, every output bit of the generator is a degree k polynomial in the input bits). For k constant we get that n = Omega(m/log(1/epsi))k, which is nearly optimal. Our result also separates degree k generators from generators in NCk0, showing that the stretch of the former can be much larger than the stretch of the latter. The problem of constructing degree k generators was introduced by Mossel et al. (2003) who gave a construction only for the case of degree 2 generators