Constructions of Low-degree and Error-Correcting epsilon-Biased Generators
In this work we give two new constructions of epsilon-biased generators. Our first construction significantly extends a result of Mossel et al. (Random Structures and Algorithms 2006, pages 56-81), and our second construction answers an open question of Dodis and Smith (STOC 2005, pages 654-663). In particular we obtain the following results: 1.For every k = o(log n) we construct an epsilon-biased generator G : {0, 1}(m) -> {0, 1}(n) that is implementable by degree k polynomials (namely, every output bit of the generator is a degree k polynomial in the input bits). For any constant k 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. The problem of constructing degree k generators was introduced by Mossel et al. who gave a construction only for the case of k = 2. 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 algorithm runs in polynomial time in the block length of the code. Moreover, these codes have a polynomial time decoding algorithm. This answers an open question of Dodis and Smith. The paper also contains an appendix by Venkatesan Guruswami that provides an explicit construction of a family of error correcting codes of rate 1/2 that has efficient encoding and decoding algorithms and whose dual codes are also good codes.
explicit constructions error correcting codes low degree polynomials epsilon-biassed generators