Algorithmic construction of sets for k-restrictions

Noga Alon, Dana Moshkovitz, Shmuel Safra

Research output: Contribution to journalArticlepeer-review

201 Scopus citations

Abstract

This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in σ m that satisfies a given set of k-wise demands. For every k positions and every demand, there must be at least one string in the list that satisfies the demand at these positions. Problems of this form frequently arise in different fields in Computer Science. The standard approach for deterministically solving such problems is via almost k-wise independence or k-wise approximations for other distributions. We offer a generic algorithmic method that yields considerably smaller constructions. To this end, we generalize a previous work of Naor et al. [1995]. Among other results, we enhance the combinatorial objects in the heart of their method, called splitters, and construct multi-way splitters, using a new discrete version of the topological Necklace Splitting Theorem [Alon 1987]. We utilize our methods to show improved constructions for group testing [Ngo and Du 2000] and generalized hashing [Alon et al. 2003], and an improved inapproximability result for SET-COVER under the assumption P ≠ NP.

Original languageEnglish (US)
Pages (from-to)153-177
Number of pages25
JournalACM Transactions on Algorithms
Volume2
Issue number2
DOIs
StatePublished - 2006

All Science Journal Classification (ASJC) codes

  • Mathematics (miscellaneous)

Keywords

  • Almost k-wise independence
  • Derandomization
  • Generalized hashing
  • Group testing
  • Set-Cover
  • Splitter
  • k-restriction

Fingerprint Dive into the research topics of 'Algorithmic construction of sets for k-restrictions'. Together they form a unique fingerprint.

Cite this