Computer Science/Discrete Mathematics Seminar I

In distributed systems, communication between the participants in the computation is usually the most expensive part of the computation. Theoretical models of distributed systems usually reflect this by neglecting the cost of local computation, and charging only for messages sent between the participants; in particular, we usually assume that the computation proceeds in rounds, and in each round each participant can send only a limited number of bits. We are interested in characterizing the number of rounds required to perform various tasks. 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.