Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs (Q2216926)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs |
scientific article |
Statements
Number on the forehead protocols yielding dense Ruzsa-Szemerédi graphs and hypergraphs (English)
0 references
18 December 2020
0 references
The authors describe algorithmic Number On the Forehead protocols in communication complexity terms that provide dense Ruzsa-Szemerédi graphs. The approach avoids the use of Behrend's construction of a large set of integers with no three-term arithmetic progressions. The results are generalized to uniform hypergraphs by extending the protocols to any number of players.
0 references
Ruzsa-Szemerédi graph
0 references
induced matching
0 references
communication complexity
0 references
NOF protocol
0 references
0 references
0 references
