@conference {17660,
title = {Splitters and near-optimal derandomization},
booktitle = {, 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings},
year = {1995},
month = {1995/10/23/25},
pages = {182 - 191},
publisher = {IEEE},
organization = {IEEE},
abstract = {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 2k 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},
keywords = {Boosting, Circuit testing, computational complexity, computational linguistics, Computer science, Contracts, derandomization, deterministic constructions, Educational institutions, Engineering profession, exhaustive testing, fairly general method, fixed-subgraph finding algorithms, hardness of approximation, Information systems, k-restrictions, learning, local-coloring protocol, MATHEMATICS, near-optimal constructions, near-optimal derandomization, Parallel algorithms, probabilistic bound, probability, Protocols, randomised algorithms, Set cover, splitters},
isbn = {0-8186-7183-1},
doi = {10.1109/SFCS.1995.492475},
author = {Naor,M. and Schulman,L. J and Srinivasan, Aravind}
}