Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published October 1995 | public
Book Section - Chapter

Splitters and near-optimal derandomization


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.

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

Additional details

August 20, 2023
October 24, 2023