The communication complexity of distributed subgraph detection
In this talk we discuss the complexity of distributed subgraph detection: there are \(n\) servers, each representing a node in an undirected graph, and each server receives as input its adjacent edges in the graph. The goal of the computation is to determine whether the global input graph contains some fixed subgraph.
In the talk I will describe upper and lower bounds for several classes of subgraphs, through a connection to Turan numbers. The general case remains open. We also point out a connection between this problem and number-on-forehead communication complexity, through which we are able to obtain a tight lower bound on deterministic triangle detection.