Learning and Verifying Graphs Using Queries with a Focus on Edge Counting

DOI10.1007/978-3-540-75225-7_24zbMath1142.68404OpenAlexW1532569127MaRDI QIDQ3520066

Nikhil Srivastava, Lev Reyzin

Publication date: 19 August 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75225-7_24

Mathematics Subject Classification ID

Computational learning theory (68Q32) Graph theory (including graph drawing) in computer science (68R10)

Related Items

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, Linear Time Constructions of Some $$d$$-Restriction Problems, Reconstructing Markov processes from independent and anonymous experiments, Non-adaptive learning of a hidden hypergraph, Unnamed Item, Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions, Reconstruction and verification of chordal graphs with a distance oracle, Network construction with subgraph connectivity constraints, Optimal query complexity bounds for finding graphs, Network verification via routing table queries, Reconstructing Weighted Graphs with Minimal Query Complexity, Unnamed Item, Non-adaptive Learning of a Hidden Hypergraph, Topology discovery of sparse random graphs with few participants, On Parity Check (0,1)-Matrix over $\mathbb{Z}_p$

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the longest path algorithm for reconstructing trees from distance matrices
• An optimal algorithm to reconstruct trees from additive distance data
• Reconstructing a Hamiltonian cycle by querying the graph: Application to DNA physical mapping
• Property testing and its connection to learning and approximation
• Learning a Hidden Matching
• Learning Theory
• Learning a Hidden Subgraph
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Optimal reconstruction of graphs under the additive model