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
- Video from the lecture [mp4].
Last changed
April 17, 2016 22:27 Europe/Helsinki (GMT +03:00)
by
local organizers, ewscs15(at)cs.ioc.ee
EWSCS'15 page:
//cs.ioc.ee/ewscs/2015/