License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2021.2
URN: urn:nbn:de:0030-drops-142760
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14276/
Linial, Nati ;
Shraibman, Adi
An Improved Protocol for the Exactly-N Problem
Abstract
In the 3-players exactly-N problem the players need to decide whether x+y+z = N for inputs x,y,z and fixed N. This is the first problem considered in the multiplayer Number On the Forehead (NOF) model. Even though this is such a basic problem, no progress has been made on it throughout the years. Only recently have explicit protocols been found for the first time, yet no improvement in complexity has been achieved to date. The present paper offers the first improved protocol for the exactly-N problem. This improved protocol has also interesting consequences in additive combinatorics. As we explain below, it yields a higher lower bound on the possible density of corner-free sets in [N]×[N].
BibTeX - Entry
@InProceedings{linial_et_al:LIPIcs.CCC.2021.2,
author = {Linial, Nati and Shraibman, Adi},
title = {{An Improved Protocol for the Exactly-N Problem}},
booktitle = {36th Computational Complexity Conference (CCC 2021)},
pages = {2:1--2:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-193-1},
ISSN = {1868-8969},
year = {2021},
volume = {200},
editor = {Kabanets, Valentine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14276},
URN = {urn:nbn:de:0030-drops-142760},
doi = {10.4230/LIPIcs.CCC.2021.2},
annote = {Keywords: Communication complexity, Number-On-the-Forehead, Corner-free sets}
}
|
Keywords: |
|
Communication complexity, Number-On-the-Forehead, Corner-free sets |
|
Collection: |
|
36th Computational Complexity Conference (CCC 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
08.07.2021 |
