Polynomial Time Optimal Query Algorithms for Finding Graphs with Arbitrary Real Weights
Proceedings of the 26th Annual Conference on Learning Theory, PMLR 30:797-818, 2013.
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.