Linear Time Constructions of Some d-Restriction Problems
From MaRDI portal
Linear Time Constructions of Some $$d$$-Restriction Problems
Abstract: We give new linear time globally explicit constructions for perfect hash families, cover-free families and separating hash functions.
Cites work
- A bound on the size of separating hash families
- A class of error-correcting pooling designs over complexes
- A group testing method for finding patterns in data
- A survey on nonadaptive group testing algorithms through the angle of decoding
- Algorithmic construction of sets for k -restrictions
- Automata, Languages and Programming
- Bounds for separating hash families
- Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
- Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Efficient computation of representative sets with applications in parameterized and exact algorithms
- Efficient Multiplicative Sharing Schemes
- Efficiently decodable non-adaptive group testing
- Explicit construction of exponential sized families of k-independent sets
- Explicit constructions for perfect hash families
- Explicit constructions of perfect hash families from algebraic curves over finite fields
- Explicit constructions of separating hash families from algebraic curves over finite fields
- Explicit Nonadaptive Combinatorial Group Testing Schemes
- Families of finite sets in which no intersection of sets is covered by the union of s others
- Fredman–Komlós bounds and information theory
- Geometric constructions of optimal linear perfect hash families
- Graph-Theoretic Concepts in Computer Science
- scientific article; zbMATH DE number 5957397 (Why is no real title available?)
- scientific article; zbMATH DE number 3887059 (Why is no real title available?)
- scientific article; zbMATH DE number 4135867 (Why is no real title available?)
- scientific article; zbMATH DE number 1228785 (Why is no real title available?)
- scientific article; zbMATH DE number 1261820 (Why is no real title available?)
- scientific article; zbMATH DE number 1024079 (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 1759788 (Why is no real title available?)
- scientific article; zbMATH DE number 3801449 (Why is no real title available?)
- scientific article; zbMATH DE number 1418320 (Why is no real title available?)
- scientific article; zbMATH DE number 5262869 (Why is no real title available?)
- Key storage in secure networks
- Learning a hidden graph using \(O(\log n)\)queries per edge
- Learning a Hidden Matching
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
- Multireceiver authentication codes: Models, bounds, constructions, and extensions
- New bounds for perfect hashing via information theory
- Non-adaptive complex group testing with multiple positive sets
- Nonrandom binary superimposed codes
- On r-cover-free families
- On generalized separating hash families
- On key storage in secure networks
- On some methods for unconditionally secure key distribution and broadcast encryption
- On the Size of Separating Systems and Families of Perfect Hash Functions
- Optimal linear perfect hash families
- Optimal linear perfect hash families with small parameters
- Perfect hash families, identifiable parent property codes and covering arrays.
- Perfect hash families: Probabilistic methods and explicit constructions
- Perfect hashing
- Perfect Hashing and Probability
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Reconstruction of hidden graphs and threshold group testing
- 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
- Some new results on key distribution patterns and broadcast encryption
- Testers and their applications
- The difference between consecutive primes. II
Cited in
(16)- Non-adaptive learning of a hidden hypergraph
- Structure-aware combinatorial group testing: a new method for pandemic screening
- Low-weight superimposed codes and related combinatorial structures: bounds and applications
- Two edge-disjoint paths with length constraints
- Exact learning from an honest teacher that answers membership queries
- Non-adaptive learning of a hidden hypergraph
- Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
- Algorithmic construction of sets for k -restrictions
- How hard is it to satisfy (almost) all roommates?
- Error-tolerant non-adaptive learning of a hidden hypergraph
- Almost optimal cover-free families
- Bounds and algorithms for generalized superimposed codes
- A survey of cover-free families: constructions, applications, and generalizations
- Adaptive exact learning of decision trees from membership queries
- On learning graphs with edge-detecting queries
- Cover-free families on hypergraphs and combinatorial group testing
This page was built for publication: Linear Time Constructions of Some $$d$$-Restriction Problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947011)
