Combinatorics: Klim Efremenko (TAU) " Testing Equality in Communication Graphs"

Speaker: Klim Efremenko (TAU)
Title: Testing Equality in Communication Graphs
Let G=(V,E) be a connected undirected graph with k vertices. Suppose
that on each vertex of the graph there is a player having an n-bit
string. Each player is allowed to communicate with its neighbors
according to a (static) agreed communication protocol and the players
must decide, deterministically, if their inputs are all equal. What
is the minimum possible total number of bits transmitted in a protocol
solving this problem? We determine this minimum up to a lower order
additive term in many cases (but not for all graphs). In particular,
we show that it is kn/2+o(n) for any Hamiltonian k-vertex graph and
that for any 2-edge connected graph with m edges containing no two
adjacent vertices of degree exceeding 2 it is mn/2+o(n).
The proofs combine graph theoretic ideas with tools from additive
number theory.
Joint work with Noga Alon and Benny Sudakov.


Mon, 05/12/2016 - 11:00 to 13:00


B220 Rothberg (CS)