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/sup 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 /spl Sigma/II/spl Sigma/ 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.

Authors

• Moni Naor
• Leonard J. Schulman
• Aravind Srinivasan

Keywords

• Computer science
• Circuit testing
• Mathematics
• Protocols
• Engineering profession
• Information systems
• Contracts
• Educational institutions
• Boosting
• Parallel algorithms
• Family Functioning
• Set Of Covariates
• Hash Function
• Universal Set
• Collection Of Vectors
• Random Variables
• Universe
• Family Size
• Efficient Algorithm
• Time Complexity
• Small Space
• Linear Time
• Probability Space
• Set Of Constructs
• Codeword
• Parallel Algorithm
• Local Construction
• Explicit Construction
• Alphabet Size
• N Log N
• Set Cover Problem