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 (16)

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

This page was built for publication: Learning and Verifying Graphs Using Queries with a Focus on Edge Counting