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 $\Sigma \Pi \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.