Reducing the seed length in the Nisan-Wigderson generator
type: Item
instance of: scholarly article
title: Reducing the seed length in the Nisan-Wigderson generator
zbMATH Open document ID: 1121.68052
author: Russell Impagliazzo
author: Ronen Shaltiel
author: A. Wigderson
published in: Combinatorica
publication date: 2007-05-08T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q15
zbMATH DE Number: 5150178
zbMATH Keywords: pseudo-random generator
zbMATH Keywords: optimal seed length
zbMATH Keywords: explicit construction
reviewed by: Jozef Vyskoč
MaRDI profile type: Publication
full work available at URL: s00493-006-0036-8
OpenAlex ID: W2033385084
DOI: 10.1007/S00493-006-0036-8
description: scientific article; zbMATH DE number 5150178