Linear Time Constructions of Some $$d$$-Restriction Problems
From MaRDI portal
Publication:2947011
DOI10.1007/978-3-319-18173-8_5zbMath1459.68150arXiv1406.2108OpenAlexW935545063MaRDI QIDQ2947011
Publication date: 21 September 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1406.2108
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Randomized algorithms (68W20)
Related Items
Almost Optimal Cover-Free Families, Exact learning from an honest teacher that answers membership queries, Exact learning of juntas from membership queries, Structure-aware combinatorial group testing: a new method for pandemic screening, Bounds and algorithms for generalized superimposed codes, Unnamed Item, Non-adaptive learning of a hidden hypergraph, How hard is it to satisfy (almost) all roommates, Low-weight superimposed codes and related combinatorial structures: bounds and applications, Non-adaptive Learning of a Hidden Hypergraph, Two edge-disjoint paths with length constraints
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Non-adaptive complex group testing with multiple positive sets
- Families of finite sets in which no intersection of \(\ell\) sets is covered by the union of \(s\) others
- Reconstruction of hidden graphs and threshold group testing
- Explicit constructions of separating hash families from algebraic curves over finite fields
- Learning a hidden graph using \(O(\log n)\)queries per edge
- A bound on the size of separating hash families
- A class of error-correcting pooling designs over complexes
- Explicit constructions for perfect hash families
- Explicit construction of exponential sized families of k-independent sets
- Key storage in secure networks
- New bounds for perfect hashing via information theory
- Some new results on key distribution patterns and broadcast encryption
- Optimal linear perfect hash families
- Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
- Sets pooling designs
- On some methods for unconditionally secure key distribution and broadcast encryption
- Perfect hashing
- Secure frameproof codes, key distribution patterns, group testing algorithms and related structures
- Perfect hash families: Probabilistic methods and explicit constructions
- Multireceiver authentication codes: Models, bounds, constructions, and extensions
- A group testing method for finding patterns in data
- On key storage in secure networks
- On \(r\)-cover-free families
- Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions
- Some new bounds for cover-free families
- Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
- A survey on nonadaptive group testing algorithms through the angle of decoding
- Bounds for separating hash families
- On generalized separating hash families
- Geometric constructions of optimal linear perfect hash families
- The Difference Between Consecutive Primes, II
- Efficient Multiplicative Sharing Schemes
- Algorithmic construction of sets for k -restrictions
- Testers and their applications
- On the Size of Separating Systems and Families of Perfect Hash Functions
- Small-Bias Probability Spaces: Efficient Constructions and Applications
- Optimal linear perfect hash families with small parameters
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- Fredman–Komlós bounds and information theory
- Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
- Perfect Hashing and Probability
- Combinatorial Properties and Constructions of Traceability Schemes and Frameproof Codes
- Learning a Hidden Matching
- Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
- Explicit Nonadaptive Combinatorial Group Testing Schemes
- Nonrandom binary superimposed codes
- Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
- Automata, Languages and Programming
- Graph-Theoretic Concepts in Computer Science
- Explicit constructions of perfect hash families from algebraic curves over finite fields
