Organizing Committee
Abstract

How can we handle graph problems when the graph is only known imperfectly?

In one setting, the input is a noisy version of some unknown ground truth graph, to which random edges have been added, destroying the structure : planarity, clustering, distances for example. In another setting, the graph itself can only be accessed via queries such as shortest path queries, distance queries, or cut queries, and must be inferred from the result to well-chosen queries ; this comes up in internet tomography. In a third setting, the graph evolves dynamically over time and solutions must adapt to edge additions and removals.

The cluster will gather researchers around a bi-weekly working group drawing on the skills of the participants in random graphs and discrete probability, optimization and linear, semi-definite or convex programming methods, structural graph properties, and randomized dynamic data structures.

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Associated Semester Workshops

Network Science and Graph Algorithms
Image for "Network Science and Graph Algorithms"
Semidefinite Programming and Graph Algorithms
Image for "Semidefinite Programming and Graph Algorithms"
Stochastic Graph Models
Image for "Stochastic Graph Models"

Research Clusters