Speaker: Klim Efremenko (TAU)

Title: Testing Equality in Communication Graphs

Abstract:

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.

Title: Testing Equality in Communication Graphs

Abstract:

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.

## Date:

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

## Location:

B220 Rothberg (CS)