Non-adaptive learning of a hidden hypergraph

DOI10.1016/j.tcs.2017.11.019zbMath1388.68146OpenAlexW2775775109MaRDI QIDQ1704557

Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi

Publication date: 12 March 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.11.019

zbMATH Keywords

perfect hash familyhypergraphsgroup testingcover-free familynon-adaptive learningmonotone DNF

Mathematics Subject Classification ID

Computational learning theory (68Q32) Hypergraphs (05C65)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Non-adaptive complex group testing with multiple positive sets
• Learning a hidden graph
• 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
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Sets pooling designs
• Trivial two-stage group testing for complexes using almost disjunct matrices.
• On a bound of cover-free families
• A group testing method for finding patterns in data
• Asking questions to minimize errors
• Some new bounds for cover-free families
• Queries and concept learning
• Construction of \(d(H)\)\,-\,disjunct matrix for group testing in hypergraphs
• A survey on nonadaptive group testing algorithms through the angle of decoding
• Exact Learning from Membership Queries: Some Techniques, Results and New Directions
• On Exact Learning Monotone DNF from Membership Queries
• Algorithmic construction of sets for k -restrictions
• Linear Time Constructions of Some $$d$$-Restriction Problems
• Testers and their applications
• Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
• Learning a Hidden Matching
• Almost Optimal Cover-Free Families
• Learning a Hidden Subgraph
• Nonrandom binary superimposed codes
• Efficient Computation of Representative Sets with Applications in Parameterized and Exact Algorithms
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Non-adaptive learning of a hidden hypergraph