A Caltech Library Service

Reconstructive Dispersers and Hitting Set Generators

Umans, Christopher (2005) Reconstructive Dispersers and Hitting Set Generators. In: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. No.3624. Springer , Berlin, pp. 460-471. ISBN 978-3-540-28239-6.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


We give a generic construction of an optimal hitting set generator (HSG) from any good “reconstructive” disperser. Past constructions of optimal HSGs have been based on such disperser constructions, but have had to modify the construction in a complicated way to meet the stringent efficiency requirements of HSGs. The construction in this paper uses existing disperser constructions with the “easiest” parameter setting in a black-box fashion to give new constructions of optimal HSGs without any additional complications. Our results show that a straightforward composition of the Nisan-Wigderson pseudorandom generator that is similar to the composition in works by Impagliazzo, Shaltiel and Wigderson in fact yields optimal HSGs (in contrast to the “near-optimal” HSGs constructed in those works). Our results also give optimal HSGs that do not use any form of hardness amplification or implicit list-decoding – like Trevisan’s extractor, the only ingredients are combinatorial designs and any good list-decodable error-correcting code.

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access ItemJournal Article
Additional Information:© 2005 Springer-Verlag Berlin Heidelberg. We thank Ronen Shaltiel for his comments on an early draft of this paper.
Subject Keywords:Pseudorandom Generator; 40th Annual IEEE Symposium; Oracle Access; Time Poly; Advice String
Series Name:Lecture Notes in Computer Science
Issue or Number:3624
Record Number:CaltechAUTHORS:20200609-101642741
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:103795
Deposited By: Tony Diaz
Deposited On:09 Jun 2020 18:07
Last Modified:16 Nov 2021 18:25

Repository Staff Only: item control page