Number on the Forehead Protocols yielding dense Ruzsa–Szemerédi graphs and hypergraphs

N. Alon, A. Shraibman

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


We describe algorithmic Number On the Forehead protocols thatprovide dense Ruzsa–Szemerédi graphs. One protocol leads to a simple and natural extension of the original construction of Ruzsa and Szemerédi.The graphs induced by this protocol have n vertices, Ω (n2/ log n) edges, and are decomposable into n1+O(1/loglogn) induced matchings.Another protocol is a somewhat simpler version of theconstruction of [1], producing graphs with similar properties.We also generalize the above protocols to morethan three players, in orderto construct dense uniformhypergraphs in which every edge lies in a positivesmall number of simplices, extending a result of Fox and Loh.

Original languageEnglish (US)
Pages (from-to)488-506
Number of pages19
JournalActa Mathematica Hungarica
Issue number2
StatePublished - Aug 1 2020

All Science Journal Classification (ASJC) codes

  • General Mathematics


  • NOF protocol
  • Ruzsa–Szemerédi graph
  • communication complexity
  • induced matching


Dive into the research topics of 'Number on the Forehead Protocols yielding dense Ruzsa–Szemerédi graphs and hypergraphs'. Together they form a unique fingerprint.

Cite this