Testing Equality in Communication Graphs

Noga Alon, Klim Efremenko, Benny Sudakov

Research output: Contribution to journalArticle

4 Scopus citations

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. 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.

Original languageEnglish (US)
Article number8016410
Pages (from-to)7569-7574
Number of pages6
JournalIEEE Transactions on Information Theory
Volume63
Issue number11
DOIs
StatePublished - Nov 2017
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Keywords

  • 2-connected graphs
  • Communication complexity
  • equality function
  • static protocols

Fingerprint Dive into the research topics of 'Testing Equality in Communication Graphs'. Together they form a unique fingerprint.

  • Cite this