TY - GEN

T1 - The power of super-logarithmic number of players

AU - Chattopadhyay, Arkadev

AU - Saks, Michael E.

N1 - Publisher Copyright:
© Arkadev Chattopadhyay and Michael E. Saks.

PY - 2014/9/1

Y1 - 2014/9/1

N2 - In the 'Number-on-Forehead' (NOF) model of multiparty communication, the input is a κ × m boolean matrix A (where κ 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 κ exceeds logm. 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 ○ g where f is a symmetric b-variate function, and g is a kr-variate function and (f○g)(A) is defined, for a k×br matrix to be f(g(A1), g(Ab)) where Ai is the i-th κ ×r block of A. Our protocol works provided that κ > 1+ln b+2r. Ada et al. [2] previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width r = 1. The new protocol is the first to work for block composed functions with r > 1. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

AB - In the 'Number-on-Forehead' (NOF) model of multiparty communication, the input is a κ × m boolean matrix A (where κ 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 κ exceeds logm. 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 ○ g where f is a symmetric b-variate function, and g is a kr-variate function and (f○g)(A) is defined, for a k×br matrix to be f(g(A1), g(Ab)) where Ai is the i-th κ ×r block of A. Our protocol works provided that κ > 1+ln b+2r. Ada et al. [2] previously obtained simultaneous and deterministic efficient protocols for composed functions of block-width r = 1. The new protocol is the first to work for block composed functions with r > 1. Moreover, it is simultaneous, with vanishingly small error probability, if public coin randomness is allowed. The deterministic and zero-error version barely uses interaction.

KW - Communication complexity

KW - Composed functions

KW - Number-On-Forehead model

UR - http://www.scopus.com/inward/record.url?scp=84920183020&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84920183020&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.APPROX-RANDOM.2014.596

DO - 10.4230/LIPIcs.APPROX-RANDOM.2014.596

M3 - Conference contribution

AN - SCOPUS:84920183020

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 596

EP - 603

BT - Leibniz International Proceedings in Informatics, LIPIcs

A2 - Jansen, Klaus

A2 - Rolim, Jose D. P.

A2 - Devanur, Nikhil R.

A2 - Moore, Cristopher

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2014 and the 18th International Workshop on Randomization and Computation, RANDOM 2014

Y2 - 4 September 2014 through 6 September 2014

ER -