%0 Conference Paper
%B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
%D 1995
%T Splitters and near-optimal derandomization
%A Naor,M.
%A Schulman,L. J
%A Srinivasan, Aravind
%K Boosting
%K Circuit testing
%K computational complexity
%K computational linguistics
%K Computer science
%K Contracts
%K derandomization
%K deterministic constructions
%K Educational institutions
%K Engineering profession
%K exhaustive testing
%K fairly general method
%K fixed-subgraph finding algorithms
%K hardness of approximation
%K Information systems
%K k-restrictions
%K learning
%K local-coloring protocol
%K MATHEMATICS
%K near-optimal constructions
%K near-optimal derandomization
%K Parallel algorithms
%K probabilistic bound
%K probability
%K Protocols
%K randomised algorithms
%K Set cover
%K splitters
%X 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
%B , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
%I IEEE
%P 182 - 191
%8 1995/10/23/25
%@ 0-8186-7183-1
%G eng
%R 10.1109/SFCS.1995.492475