Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights

Sung-Soon Choi
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:797-818, 2013.

Abstract

We consider the problem of finding the edges of a hidden weighted graph and their weights by using a certain type of queries as few times as possible, with focusing on two types of queries with additive property. For a set of vertices, the additive query asks the sum of weights of the edges with both ends in the set. For a pair of disjoint sets of vertices, the cross-additive query asks the sum of weights of the edges crossing between the two sets. These queries were motivated by DNA sequencing, population genetics, and artificial intelligence, and have been paid considerable attention to in computational learning. In this paper, we achieve an ultimate goal of recent years for graph finding with the two types of queries, by constructing the first polynomial time algorithms with optimal query complexity for the general class of graphs with n vertices and at most m edges in which the weights of edges are arbitrary real numbers. The algorithms are randomized and their query complexities are O(\fracm \log n\log m). These bounds improve the best known by a factor of \log m, and settle the open problem posed in some papers including [Choi and Kim, Optimal query complexity bounds for finding graphs, STOC 2008]. To build key components for graph finding, we consider the coin weighing problem with a spring scale. The problem itself has been paid much attention to in a long history of combinatorial search. We construct the first polynomial time algorithm with optimal query complexity for the general case in which the weight differences between counterfeit and authentic coins are arbitrary real numbers. We also construct the first polynomial time optimal query algorithm for finding the Fourier coefficients of a certain class of pseudo-Boolean functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v30-Choi13, title = {Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights}, author = {Choi, Sung-Soon}, booktitle = {Proceedings of the 26th Annual Conference on Learning Theory}, pages = {797--818}, year = {2013}, editor = {Shalev-Shwartz, Shai and Steinwart, Ingo}, volume = {30}, series = {Proceedings of Machine Learning Research}, address = {Princeton, NJ, USA}, month = {12--14 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v30/Choi13.pdf}, url = {https://proceedings.mlr.press/v30/Choi13.html}, abstract = {We consider the problem of finding the edges of a hidden weighted graph and their weights by using a certain type of queries as few times as possible, with focusing on two types of queries with additive property. For a set of vertices, the additive query asks the sum of weights of the edges with both ends in the set. For a pair of disjoint sets of vertices, the cross-additive query asks the sum of weights of the edges crossing between the two sets. These queries were motivated by DNA sequencing, population genetics, and artificial intelligence, and have been paid considerable attention to in computational learning. In this paper, we achieve an ultimate goal of recent years for graph finding with the two types of queries, by constructing the first polynomial time algorithms with optimal query complexity for the general class of graphs with n vertices and at most m edges in which the weights of edges are arbitrary real numbers. The algorithms are randomized and their query complexities are O(\fracm \log n\log m). These bounds improve the best known by a factor of \log m, and settle the open problem posed in some papers including [Choi and Kim, Optimal query complexity bounds for finding graphs, STOC 2008]. To build key components for graph finding, we consider the coin weighing problem with a spring scale. The problem itself has been paid much attention to in a long history of combinatorial search. We construct the first polynomial time algorithm with optimal query complexity for the general case in which the weight differences between counterfeit and authentic coins are arbitrary real numbers. We also construct the first polynomial time optimal query algorithm for finding the Fourier coefficients of a certain class of pseudo-Boolean functions.} }
Endnote
%0 Conference Paper %T Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights %A Sung-Soon Choi %B Proceedings of the 26th Annual Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2013 %E Shai Shalev-Shwartz %E Ingo Steinwart %F pmlr-v30-Choi13 %I PMLR %P 797--818 %U https://proceedings.mlr.press/v30/Choi13.html %V 30 %X We consider the problem of finding the edges of a hidden weighted graph and their weights by using a certain type of queries as few times as possible, with focusing on two types of queries with additive property. For a set of vertices, the additive query asks the sum of weights of the edges with both ends in the set. For a pair of disjoint sets of vertices, the cross-additive query asks the sum of weights of the edges crossing between the two sets. These queries were motivated by DNA sequencing, population genetics, and artificial intelligence, and have been paid considerable attention to in computational learning. In this paper, we achieve an ultimate goal of recent years for graph finding with the two types of queries, by constructing the first polynomial time algorithms with optimal query complexity for the general class of graphs with n vertices and at most m edges in which the weights of edges are arbitrary real numbers. The algorithms are randomized and their query complexities are O(\fracm \log n\log m). These bounds improve the best known by a factor of \log m, and settle the open problem posed in some papers including [Choi and Kim, Optimal query complexity bounds for finding graphs, STOC 2008]. To build key components for graph finding, we consider the coin weighing problem with a spring scale. The problem itself has been paid much attention to in a long history of combinatorial search. We construct the first polynomial time algorithm with optimal query complexity for the general case in which the weight differences between counterfeit and authentic coins are arbitrary real numbers. We also construct the first polynomial time optimal query algorithm for finding the Fourier coefficients of a certain class of pseudo-Boolean functions.
RIS
TY - CPAPER TI - Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights AU - Sung-Soon Choi BT - Proceedings of the 26th Annual Conference on Learning Theory DA - 2013/06/13 ED - Shai Shalev-Shwartz ED - Ingo Steinwart ID - pmlr-v30-Choi13 PB - PMLR DP - Proceedings of Machine Learning Research VL - 30 SP - 797 EP - 818 L1 - http://proceedings.mlr.press/v30/Choi13.pdf UR - https://proceedings.mlr.press/v30/Choi13.html AB - We consider the problem of finding the edges of a hidden weighted graph and their weights by using a certain type of queries as few times as possible, with focusing on two types of queries with additive property. For a set of vertices, the additive query asks the sum of weights of the edges with both ends in the set. For a pair of disjoint sets of vertices, the cross-additive query asks the sum of weights of the edges crossing between the two sets. These queries were motivated by DNA sequencing, population genetics, and artificial intelligence, and have been paid considerable attention to in computational learning. In this paper, we achieve an ultimate goal of recent years for graph finding with the two types of queries, by constructing the first polynomial time algorithms with optimal query complexity for the general class of graphs with n vertices and at most m edges in which the weights of edges are arbitrary real numbers. The algorithms are randomized and their query complexities are O(\fracm \log n\log m). These bounds improve the best known by a factor of \log m, and settle the open problem posed in some papers including [Choi and Kim, Optimal query complexity bounds for finding graphs, STOC 2008]. To build key components for graph finding, we consider the coin weighing problem with a spring scale. The problem itself has been paid much attention to in a long history of combinatorial search. We construct the first polynomial time algorithm with optimal query complexity for the general case in which the weight differences between counterfeit and authentic coins are arbitrary real numbers. We also construct the first polynomial time optimal query algorithm for finding the Fourier coefficients of a certain class of pseudo-Boolean functions. ER -
APA
Choi, S.. (2013). Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights. Proceedings of the 26th Annual Conference on Learning Theory, in Proceedings of Machine Learning Research 30:797-818 Available from https://proceedings.mlr.press/v30/Choi13.html.

Related Material