## Reconstructing Weighted Graphs with Minimal Query Complexity
n for any positive constants ^{b}a and b.
For any m there exists a non-adaptive algorithm that finds the
edges of the graph using
additive queries. This solves the open problem in [S. Choi, J. H. Kim. Optimal Query Complexity Bounds for Finding Graphs. Proc. of the 40th annual ACM Symposium on Theory of Computing , 749–758, 2008]. Choi and Kim’s proof holds for m ≥ (log n)^{α}
for a sufficiently large constant α and uses graph theory.
We use the algebraic approach for the problem.
Our proof is simple and holds for any m.
The slides of the talk presented at ALT 2009 are available.
©Copyright 2009, Springer |