Universal Sets and Cover-Free Families
Published in arXiv, 2016
Recommended citation: Saharoy, Debjyoti, and Shailesh Vaya. "Universal Sets and Cover-Free Families." arXiv preprint arXiv:1606.01376 (2016). https://arxiv.org/abs/1606.01376
Abstract: We propose a polynomial time construction of an $(n, d)$-universal set over alphabet $\Sigma={0,1}$, of size $d \cdot 2^{d+o(d)} \cdot \log n$. This is an improvement over the size, $d^5 2^{2.66 d} \log n$, of an $(n, d)$-universal set constructed by Bshouty, [1], over alphabet $\Sigma={0,1}$.
Recommended citation: Saharoy, Debjyoti, and Shailesh Vaya. “Universal Sets and Cover-Free Families.” arXiv preprint arXiv:1606.01376 (2016).