On learning graphs with edge-detecting queries

MaRDI QIDQ7034408zbMATH OpenFDO

Authors Hasan Abasi, Nader H. Bshouty

Publication date 31 January 2025

Full work available at URL https://proceedings.mlr.press/v98/abasi19a.html

zbMATH Keywords

edge-detecting queriesgraph learninggroup testingLas Vegas algorithmMonte Carlo algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Learning and adaptive systems in artificial intelligence (68T05) Randomized algorithms (68W20)

Cites work

• Bounds on the length of disjunctive codes
• Graph-Theoretic Concepts in Computer Science
• scientific article; zbMATH DE number 5957397 (Why is no real title available?)
• scientific article; zbMATH DE number 1508646 (Why is no real title available?)
• Inferring Social Networks from Outbreaks
• Learning a hidden graph using \(O(\log n)\)queries per edge
• Learning a Hidden Matching
• Learning a Hidden Subgraph
• Linear Time Constructions of Some d-Restriction Problems
• Noise-resilient group testing: limitations and constructions
• Non-adaptive learning of a hidden hypergraph
• On r-cover-free families
• On Exact Learning Monotone DNF from Membership Queries
• Pooling designs and nonadaptive group testing. Important tools for DNA sequencing.

Cited in

(4)

• Constructing large matchings via query access to a maximal matching oracle
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Lower bounds for graph reconstruction with maximal independent set queries
• Finding the diameter of a tree with distance queries

This page was built for publication: On learning graphs with edge-detecting queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7034408)