Reconstructing Graphs from Random Subgraphs.

Speaker

Andrew McGregor October 22, 2021.

Abstract

A generic problem in many areas of computer science, and beyond, is to learn from multiple noisy or partial observations. A simple example could be averaging the results of multiple noisy experiments in order to estimate the acidity of an unknown chemical. Another example could be inferring a message from multiple corrupted copies of the message. Natural questions include how many observations are required to learn with the necessary accuracy and how to efficiently make the inference from these observations. In this talk, we focus on an example from theoretical computer science: learning a graph from multiple random subgraphs where each subgraph is the induced subgraph of a set of randomly sampled nodes. We present both upper and lower bounds for a variety of families of graphs. Joint work with Rik Sengupta.