Abstract In the (k, h)-SetCover problem, we are given a collection S of sets over a universe
U, and the goal is to distinguish between the case that S contains k sets which cover U, from
the case that at least h sets in S are needed to cover U. Lin (ICALP'19) recently showed a
gap creating reduction from the (k, k+ 1)-SetCover problem on universe of size Ok (log| S|) to
the problem on universe of size| S|. In this paper, we prove a more scalable version of his
result: given any error correcting code C over alphabet [q], rate ρ, and relative distance δ, we …

In the $(k, h) $-SetCover problem, we are given a collection $\mathcal {S} $ of sets over a
universe $ U $, and the goal is to distinguish between the case that $\mathcal {S} $ contains
$ k $ sets which cover $ U $, from the case that at least $ h $ sets in $\mathcal {S} $ are
needed to cover $ U $. Lin (ICALP'19) recently showed a gap creating reduction from the
$(k, k+ 1) $-SetCover problem on universe of size $ O_k (\log|\mathcal {S}|) $ to the $\left
(k,\sqrt [k]{\frac {\log|\mathcal {S}|}{\log\log|\mathcal {S}|}}\cdot k\right) $-SetCover problem on …