### 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/