THE BNS LOWER-BOUND FOR MULTIPARTY PROTOCOLS IS NEARLY OPTIMAL

Authors
GROLMUSZ V
Citation
V. Grolmusz, THE BNS LOWER-BOUND FOR MULTIPARTY PROTOCOLS IS NEARLY OPTIMAL, Information and computation, 112(1), 1994, pp. 51-54
Citations number
7
Categorie Soggetti
Information Science & Library Science",Mathematics,"Computer Science Information Systems
Journal title
Information and computation → ACNP
ISSN journal
08905401
Volume
112
Issue
1
Year of publication
1994
Pages
51 - 54
Database
ISI
SICI code
0890-5401(1994)112:1<51:TBLFMP>2.0.ZU;2-1
Abstract
We present a multi-party protocol which computes the Generalized Inner Product (GIP) function, introduced by Babai et al. (1989, in ''Procee dings, 21st ACM STOC,'' pp. 1-11). Our protocol shows that the lower b ound for the multi-party communication complexity of the GIP function, given by Babai et al., cannot be improved significantly. (C) 1994 Aca demic Press, Inc.