Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
Abstract
We consider the problem of learning and verifying hidden graphs and their properties given query access to the graphs. We analyze various queries (edge detection, edge counting, shortest path), but we focus mainly on edge counting queries. We give an algorithm for learning graph partitions using O ( n log n ) edge counting queries. We introduce a problem that has not been considered: verifying graphs with edge counting queries, and give a randomized algorithm with error ε for graph verification using O (log(1/ ε )) edge counting queries. We examine the current state of the art and add some original results for edge detection and shortest path queries to give a more complete picture of the relative power of these queries to learn various graph classes. Finally, we relate our work to Freivalds’ ‘fingerprinting technique’ – a probabilistic method for verifying that two matrices are equal by multiplying them by random vectors.
Cite
Text
Reyzin and Srivastava. "Learning and Verifying Graphs Using Queries with a Focus on Edge Counting." International Conference on Algorithmic Learning Theory, 2007. doi:10.1007/978-3-540-75225-7_24Markdown
[Reyzin and Srivastava. "Learning and Verifying Graphs Using Queries with a Focus on Edge Counting." International Conference on Algorithmic Learning Theory, 2007.](https://mlanthology.org/alt/2007/reyzin2007alt-learning/) doi:10.1007/978-3-540-75225-7_24BibTeX
@inproceedings{reyzin2007alt-learning,
title = {{Learning and Verifying Graphs Using Queries with a Focus on Edge Counting}},
author = {Reyzin, Lev and Srivastava, Nikhil},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2007},
pages = {285-297},
doi = {10.1007/978-3-540-75225-7_24},
url = {https://mlanthology.org/alt/2007/reyzin2007alt-learning/}
}