Reconstructing Graphs from Random Subgraphs.


Andrew McGregor October 22, 2021.


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.

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Collaborative Top Distribution Identifications with Limited Interaction
  • Brooks' Theorem in Graph Streams, A Single-Pass Semi-Streaming Algorithm for Δ-Coloring
  • Deterministic identity testing paradigms for bounded top-fanin depth-4 circuits
  • Why we couldn't prove SETH hardness of CVP for even norms, Subset-SUM, and Many more!
  • On Probabilistic Approximations of Boolean Functions via Polynomials, and Polynomial Closure Statements over the Boolean Cube