Learning a hidden graph using \(O(\log n)\)queries per edge
From MaRDI portal
Publication:927873
DOI10.1016/j.jcss.2007.06.006zbMath1147.68033OpenAlexW2080318337MaRDI QIDQ927873
Publication date: 10 June 2008
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2007.06.006
graphshypergraphsquery learningchemical reaction networksedge-detecting queriesmonotone DNF formulas
Related Items
Almost Optimal Cover-Free Families, A divide-and-conquer approach for reconstruction of \(\{C_{ \geq 5}\}\)-free graphs via betweenness queries, Exact learning from an honest teacher that answers membership queries, Learning Boolean halfspaces with small weights from membership queries, Linear Time Constructions of Some $$d$$-Restriction Problems, Unnamed Item, Reconstructing Markov processes from independent and anonymous experiments, Non-adaptive learning of a hidden hypergraph, Learning a hidden graph, Recovering Social Networks from Individual Attributes, Learning a hidden uniform hypergraph, Network construction with subgraph connectivity constraints, Reconstruction of hidden graphs and threshold group testing, COMPETITIVE GROUP TESTING AND LEARNING HIDDEN VERTEX COVERS WITH MINIMUM ADAPTIVITY, Finding hidden hubs and dominating sets in sparse graphs by randomized neighborhood queries, Unnamed Item, Non-adaptive Learning of a Hidden Hypergraph
Cites Work