Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
An algebraic approach to communication complexity
| |
|
An algebraic approach to communication complexity
Jean-FranÇois Raymond1  , Pascal Tesson1 and Denis Thérien1
| (1) |
School of Computer Science, McGill University, 3480 rue University, H3A 2A7 Montréal (PQ), Canada |
Abstract
Let M be a finite monoid: define C (k)( M) to be the maximum number of bits that need to be exchanged in the k-party communication game to decide membership in any language recognized by M. We prove the following:
| a) |
If M is a group then, for any k, C(k)(M) = O(1) if M is nilpotent of class k − 1 and C(k)(M) = θ(n) otherwise.
|
| b) |
If M is aperiodic, then C(2)(M) = O(1) if M is commutative, C(2)(M) = θ(log n) if M belongs to the variety DA but is not commutative and C(2)(M) = θ(n) otherwise.
|
We also show that when M is in DA, C(k)(M) = O(1) for some k and conjecture that this algebraic condition is also necessary.
Research supported by FCAR and NSERC grants. We would like to thank Peter Bro Miltersen of the University of Aarhus, Denmark
for his ideas and comments, that helped us improve some of our lower bounds.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|