Christoph Lenzen gives the following guest lecture on Thursday, 11 October 2012, at 2:15pm in room C220. The lecture is part of the seminar course on distributed algorithms.
Abstract. In the past decades, excessive amounts of research have been dedicated to determining the distributed time complexity of basic graph theoretical problems. However, there is little understanding of the influence of restricting the bandwidth of communication. Once messages are of size O(log n) (where n is the number of nodes in the system), existing lower bounds argue about particular graphs exhibiting communication bottle necks. In this talk, we consider a fully connected system, i.e., there is no communication bottleneck.
We examine how fast one can compute, given the neighborhood in some input graph to each node, whether there is a triangle in the input graph. We discuss a number of non-trivial upper bounds; for instance, one can answer the question within O(n1/3) rounds deterministically. This might surprise at first glance, since one might expect either linear or constant time complexity. This hints at the possibility of a "coordination lower bound" that does not arise from a communication bottleneck.
Biography. Christoph Lenzen received a diploma degree in Mathematics from the University of Bonn, Germany, and subsequently performed his graduate studies in Distributed Computing in the group of Professor Roger Wattenhofer at ETH Zurich. In 2011, he was a postdoctoral Fellow at the Hebrew University of Jerusalem, with Danny Dolev. Currently, he is a postdoctoral fellow at the Weizmann Institute of Science, with Professor David Peleg. In 2012 and 2013 he will be a postdoctoral fellow at MIT, with Professor Nancy Lynch. His research interests cover distributed computing in a wider sense, including topics such as randomized load balancing, graph algorithms, and clock synchronization. He published e.g. at PODC, SPAA, FOCS, and STOC, and in JACM. In 2009, he and his coauthors received the PODC best paper award for their work on gradient clock synchronization.