A Caltech Library Service

Splitters and near-optimal derandomization

Naor, Moni and Schulman, Leonard J. and Srinivasan, Aravind (1995) Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science. IEEE Computer Society Press , Los Alamitos, CA, pp. 182-191. ISBN 0-8186-7183-1.

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

Use this Persistent URL to link to this item:


We present a fairly general method for finding deterministic constructions obeying what we call k-restrictions; this yields structures of size not much larger than the probabilistic bound. The structures constructed by our method include (n,k)-universal sets (a collection of binary vectors of length n such that for any subset of size k of the indices, all 2^k configurations appear) and families of perfect hash functions. The near-optimal constructions of these objects imply the very efficient derandomization of algorithms in learning, of fixed-subgraph finding algorithms, and of near optimal ΣIIΣ threshold formulae. In addition, they derandomize the reduction showing the hardness of approximation of set cover. They also yield deterministic constructions for a local-coloring protocol, and for exhaustive testing of circuits.

Item Type:Book Section
Related URLs:
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:© 1995 IEEE. Date of Current Version: 06 August 2002. We thank Oded Goldreich and Ravi Sundaram for explaining the implication of the construction of (n,k)-universal sets to the non-approximability of set cover; and we thank Mike Luby for a discussion. We thank Uri Feige for explaining his results. Supported by an Alon Fellowship and by a grant from the Israel Science Foundation administered by the Israeli Academy of Sciences
Funding AgencyGrant Number
Alon FellowshipUNSPECIFIED
Israel Science Foundation (ISF)UNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number5125637
Record Number:CaltechAUTHORS:20120223-112750729
Persistent URL:
Official Citation:Naor, M.; Schulman, L.J.; Srinivasan, A.; , "Splitters and near-optimal derandomization," Foundations of Computer Science, 1995. Proceedings., 36th Annual Symposium on , vol., no., pp.182-191, 23-25 Oct 1995 doi: 10.1109/SFCS.1995.492475 URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:29440
Deposited By: Ruth Sustaita
Deposited On:23 Feb 2012 21:04
Last Modified:09 Nov 2021 17:07

Repository Staff Only: item control page