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 -