Reducing the seed length in the Nisan-Wigderson generator (Q879167)

The paper is about improvement of well-known pseudo-random generators by Nissan and Wigderson (NW-generators). Particularly, by new analysis of the NW-generator it is shown that one can construct pseudo-random generators that have ''optimal'' seed length (i.e. a seed length which is linear in the optimal value). Subsequently, using known results on the connection between extractors and pseudo-random generators, the first explicit construction of an extractor is given, which uses asymptotically optimal seed length for random sources of arbitrary min-entropy. The first section (takes one third of the paper) gives brief overview of the context in which pseudo-random generators and extractors are investigated in complexity theory, main theorems formalizing new results, comparisons with previous results, as well as the sequence of ideas used to get new results presented at a semi-intuitive and semi-technical level. The rest of the paper after introducing formal definitions and necessary background (section 2) gives the main construction and proof of its correctness (section 3) and proof of the main theorems (section 4). Finally, notions of optimality for pseudo-random generator constructions are discussed (section 5) followed by a brief overview of open problems and subsequent works.