20th Estonian Winter School in Computer Science (EWSCS)
XX Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1 - 6, 2015

Ivan Rapaport

Departamento de Ingeniería Matemática
Universidad de Chile
Santiago, Chile

The broadcast congested clique model of computation

Abstract

In the broadcast congested clique model, n nodes communicate in synchronous rounds by writing O(log n)-bit messages on a whiteboard, which is visible to all of them. The joint input to the nodes is an undirected n-node graph G, with node v receiving the list of its neighbors in G. In other words, the only information each node has, besides n and its own ID, is the list of IDs of its neighbors in G. At the end of the protocol the whiteboard must contain enough information to answer a question of the form ``Does the input graph G belong to the graph class C?". In this talk we analyze natural classes (questions) that can/cannot be solved in one round.

Materials of the special lecture

Valid CSS! Valid XHTML 1.0 Strict Last changed April 17, 2016 22:27 Europe/Helsinki (GMT +03:00) by local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page: http://cs.ioc.ee/ewscs/2015/