Is there a deterministic algorithm to construct $(n,k)$-universal set of minimum size?
Such constructions appear in papers of Seroussi and Bshouty, Alon, and Naor and Naor. See Bshouty for the latest on this topic.