ICS Theory Group

June 4, Spring Quarter 2010: Theory Seminar

1:00pm in ICS 243

Optimally Reconstructing Weighted Graphs Using Queries

Maury Gridley

Presenting a SODA 2010 paper by Hanna Mazzawi.

Abstract: In this paper, we consider the problem of reconstructing a hidden graph with m edges using additive queries. Given a graph G = (V,E) and a set of vertices S subset V, an additive query, Q(S), asks for the number of edges in the subgraph induced by S. In this paper we give the first polynomial time algorithm with query complexity that matches the information theoretic lower bound.