Abstract: Roughly speaking, an -Cover Free Family (CFF) is a small set of -bit strings such that: "in any indices we see all patterns of weight ". CFFs have been of interest for a long time both in discrete mathematics as part of block design theory, and in theoretical computer science where they have found a variety of applications, for example, in parametrized algorithms where they were introduced in the recent breakthrough work of Fomin, Lokshtanov and Saurabh under the name `lopsided universal sets'. In this paper we give the first explicit construction of cover-free families of optimal size up to lower order multiplicative terms, {for any and }. In fact, our construction time is almost linear in the size of the family. Before our work, such a result existed only for . and . As a sample application, we improve the running times of parameterized algorithms from the recent work of Gabizon, Lokshtanov and Pilipczuk.
Recommendations
Cites work
- scientific article; zbMATH DE number 4135867 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1462939 (Why is no real title available?)
- scientific article; zbMATH DE number 1508646 (Why is no real title available?)
- scientific article; zbMATH DE number 3801449 (Why is no real title available?)
- scientific article; zbMATH DE number 5262869 (Why is no real title available?)
- A group testing method for finding patterns in data
- Bounds on the rate of disjunctive codes
- Collusion-secure fingerprinting for digital data
- Color-coding
- Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
- Efficient construction of a small hitting set for combinatorial rectangles in high dimension
- Efficiently decodable non-adaptive group testing
- Explicit Nonadaptive Combinatorial Group Testing Schemes
- Explicit constructions of separating hash families from algebraic curves over finite fields
- Fast algorithms for parameterized problems with relaxed disjointness constraints
- Faster Algebraic Algorithms for Path and Packing Problems
- Learning a hidden graph using \(O(\log n)\)queries per edge
- Linear Time Constructions of Some d-Restriction Problems
- Non-adaptive complex group testing with multiple positive sets
- Non-adaptive learning of a hidden hypergraph
- Nonrandom binary superimposed codes
- On r-cover-free families
- On r-Simple k-Path
- Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
- Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
- Sets pooling designs
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Some new bounds for cover-free families
- Testers and their applications
- Trivial two-stage group testing for complexes using almost disjunct matrices.
Cited in
(13)- Lower bounds for cover-free families
- Generalized cover-free families.
- A generalization of (2,w;d)-cover free families.
- How hard is it to satisfy (almost) all roommates?
- Deterministic protocols in the SINR model without knowledge of coordinates
- Error-tolerant non-adaptive learning of a hidden hypergraph
- A survey of cover-free families: constructions, applications, and generalizations
- Embedding cover-free families and cryptographical applications
- Some new bounds for cover-free families through biclique covers
- Component order connectivity in directed graphs
- Component order connectivity in directed graphs
- Non-adaptive learning of a hidden hypergraph
- Non-adaptive learning of a hidden hypergraph
This page was built for publication: Almost optimal cover-free families
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283363)
