TY - CONF
T1 - Splitters and near-optimal derandomization
T2 - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
Y1 - 1995
A1 - Naor,M.
A1 - Schulman,L. J
A1 - Srinivasan, Aravind
KW - Boosting
KW - Circuit testing
KW - computational complexity
KW - computational linguistics
KW - Computer science
KW - Contracts
KW - derandomization
KW - deterministic constructions
KW - Educational institutions
KW - Engineering profession
KW - exhaustive testing
KW - fairly general method
KW - fixed-subgraph finding algorithms
KW - hardness of approximation
KW - Information systems
KW - k-restrictions
KW - learning
KW - local-coloring protocol
KW - MATHEMATICS
KW - near-optimal constructions
KW - near-optimal derandomization
KW - Parallel algorithms
KW - probabilistic bound
KW - probability
KW - Protocols
KW - randomised algorithms
KW - Set cover
KW - splitters
AB - 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
JA - , 36th Annual Symposium on Foundations of Computer Science, 1995. Proceedings
PB - IEEE
SN - 0-8186-7183-1
M3 - 10.1109/SFCS.1995.492475
ER -