Almost optimal cover-free families

DOI10.1007/978-3-319-57586-5_13zbMATH Open1487.68259arXiv1507.07368OpenAlexW2963540524MaRDI QIDQ5283363FDOQ5283363

Authors: Nader H. Bshouty, Ariel Gabizon 

Publication date: 21 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Roughly speaking, an $(n,(r,s))$-Cover Free Family (CFF) is a small set of $n$-bit strings such that: "in any $d:=r+s$ indices we see all patterns of weight $r$". 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 $r$ and $s$}. In fact, our construction time is almost linear in the size of the family. Before our work, such a result existed only for $r=d^{o(1)}$. and $r=omega(d/(loglogdlogloglogd))$. As a sample application, we improve the running times of parameterized algorithms from the recent work of Gabizon, Lokshtanov and Pilipczuk.

Full work available at URL: https://arxiv.org/abs/1507.07368

Recommendations

• A generalization of \((2,w;d)\)-cover free families.
• Generalized cover-free families.
• Some new bounds for cover-free families through biclique covers
• Lower bounds for cover-free families
• Constructions of 2-cover-free families and related separating hash families

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Algorithms on strings (68W32) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Bounds on the rate of disjunctive codes
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Title not available (Why is that?)
• Faster Algebraic Algorithms for Path and Packing Problems
• Title not available (Why is that?)
• Color-coding
• Title not available (Why is that?)
• Nonrandom binary superimposed codes
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.
• Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
• Collusion-secure fingerprinting for digital data
• Efficient construction of a small hitting set for combinatorial rectangles in high dimension
• Title not available (Why is that?)
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Non-adaptive complex group testing with multiple positive sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Some new bounds for cover-free families
• Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
• On \(r\)-cover-free families
• Title not available (Why is that?)
• On r-Simple k-Path
• A group testing method for finding patterns in data
• Sets pooling designs
• Trivial two-stage group testing for complexes using almost disjunct matrices.
• Explicit constructions of separating hash families from algebraic curves over finite fields
• Explicit Nonadaptive Combinatorial Group Testing Schemes
• Non-adaptive Learning of a Hidden Hypergraph
• Linear Time Constructions of Some $$d$$-Restriction Problems
• Testers and their applications
• Fast Algorithms for Parameterized Problems with Relaxed Disjointness Constraints

Cited In (11)

• Title not available (Why is that?)
• Generalized cover-free families.
• Non-adaptive Learning of a Hidden Hypergraph
• Deterministic protocols in the SINR model without knowledge of coordinates
• A survey of cover-free families: constructions, applications, and generalizations
• Embedding cover-free families and cryptographical applications
• How hard is it to satisfy (almost) all roommates
• 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

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)