2026-08-16T23:12:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4724 2024-03-06T10:35:19Z ddc:004 open_access

The Power of Super-logarithmic Number of Players Chattopadhyay, Arkadev Saks, Michael E. Communication complexity Number-On-Forehead model composed functions In the `Number-on-Forehead' (NOF) model of multiparty communication, the input is a k times m boolean matrix A (where k is the number of players) and Player i sees all bits except those in the i-th row, and the players communicate by broadcast in order to evaluate a specified function f at A. We discover new computational power when k exceeds log m. We give a protocol with communication cost poly-logarithmic in m, for block composed functions with limited block width. These are functions of the form f o g where f is a symmetric b-variate function, and g is a (kr)-variate function and (f o g)(A) is defined, for a k times (br) matrix to be f(g(A-1),...,g(A-b)) where A-i is the i-th (k times r) block of A. Our protocol works provided that k > 1+ ln b + (2 to the power of r). Ada et al. (ICALP'2012) previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width one. The new protocol is the first to work for block composed functions with block-width greather than one. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Arkadev Chattopadhyay and Michael E. Saks 2014 Is Part Of LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2014.596 urn:nbn:de:0030-drops-47243 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.596 eng https://creativecommons.org/licenses/by/3.0/legalcode