Learning Graphs via Queries 690 Report
Lev Reyzin, Chen Jiang · 2007
In this report , we explore various aspects of query learning. We focus on learning hidden structures given various queries. In Chapter 1, we consider learning evolutionary trees given distance queries. In Chapter 2 we focus on learning and verifying general graph structures with various queries. In Chapter 3 we are interested in learning circuits with value-injection queries. Chapter 1 is based on a paper coauthored with Nikhil Srivastava, entitled “On the Longest Path Algorithm for Reconstructing Trees from Distance Matrices.” This paper appears in Information Processing Letters, 2007 [35]. Chapter 2 is based on a paper coauthored with Nikhil Srivastava, entitled “Learning and Verifying Graphs using Queries with a Focus on Edge Counting.” This paper has been submitted to the Symposium on Algorithmic Learning Theory, 2007 [34]. Chapter 3 is based on a paper coauthored with Dana Angluin, James Aspnes, and Jiang Chen, entitled “Learning Large-Alphabet and Analog Circuits with Value Injection Queries.” This paper appears in the Conference on Learning Theory, 2007 [5]. I would especially like to thank Dana Angluin for being such a great advisor for this 690 project (and in general). I would also like to thank Nikhil Srivastava for the close collaborations on two papers, as well as my other co-authors Jim Aspnes and Jiang Chen