# Communication Complexity and Lower Bounds on Multilective Computations

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 2, page 193-212
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHromkovič, Juraj. "Communication Complexity and Lower Bounds on Multilective Computations." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 193-212. <http://eudml.org/doc/221992>.

@article{Hromkovič2010,

abstract = {
Communication complexity of two-party (multiparty) protocols
has established itself as a successful method for proving lower
bounds on the complexity of concrete problems for numerous computing
models. While the relations between communication complexity and
oblivious, semilective computations are usually transparent and
the main difficulty is reduced to proving nontrivial lower bounds on
the communication complexity of given computing problems, the
situation essentially changes, if one considers non-oblivious or
multilective computations. The known lower bound proofs for such
computations are far from being transparent and the crucial ideas
of these proofs are often hidden behind some nontrivial
combinatorial analysis. The aim of this paper is to create a general
framework for the use of two-party communication protocols for lower
bound proofs on multilective computations. The result of this
creation is not only a transparent presentation of some known lower
bounds on the complexity of multilective computations on distinct computing
models, but also the derivation of new
nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean
circuits.
In the case of VLSI circuits we obtain a generalization of
Thompson's lower bounds on AT2 complexity for multilective circuits.
The Ω(n2) lower bound on the number of gates of any k-multilective
planar Boolean circuit computing a specific Boolean function of n variables
is established for $k<\frac\{1\}\{2\} \log_2 n$.
Another advantage of this framework is that it provides lower
bounds for a lot of concrete functions. This contrasts to the typical papers
devoted to lower bound proofs, where one establishes a lower bound for one
or a few specific functions.
},

author = {Hromkovič, Juraj},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Communication complexity; lower bounds on complexity;
Boolean functions; branching programs; circuits.; protocols; multilective computations; VLSI circuits},

language = {eng},

month = {3},

number = {2},

pages = {193-212},

publisher = {EDP Sciences},

title = {Communication Complexity and Lower Bounds on Multilective Computations},

url = {http://eudml.org/doc/221992},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Hromkovič, Juraj

TI - Communication Complexity and Lower Bounds on Multilective Computations

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 2

SP - 193

EP - 212

AB -
Communication complexity of two-party (multiparty) protocols
has established itself as a successful method for proving lower
bounds on the complexity of concrete problems for numerous computing
models. While the relations between communication complexity and
oblivious, semilective computations are usually transparent and
the main difficulty is reduced to proving nontrivial lower bounds on
the communication complexity of given computing problems, the
situation essentially changes, if one considers non-oblivious or
multilective computations. The known lower bound proofs for such
computations are far from being transparent and the crucial ideas
of these proofs are often hidden behind some nontrivial
combinatorial analysis. The aim of this paper is to create a general
framework for the use of two-party communication protocols for lower
bound proofs on multilective computations. The result of this
creation is not only a transparent presentation of some known lower
bounds on the complexity of multilective computations on distinct computing
models, but also the derivation of new
nontrivial lower bounds on multilective VLSI circuits and multilective planar Boolean
circuits.
In the case of VLSI circuits we obtain a generalization of
Thompson's lower bounds on AT2 complexity for multilective circuits.
The Ω(n2) lower bound on the number of gates of any k-multilective
planar Boolean circuit computing a specific Boolean function of n variables
is established for $k<\frac{1}{2} \log_2 n$.
Another advantage of this framework is that it provides lower
bounds for a lot of concrete functions. This contrasts to the typical papers
devoted to lower bound proofs, where one establishes a lower bound for one
or a few specific functions.

LA - eng

KW - Communication complexity; lower bounds on complexity;
Boolean functions; branching programs; circuits.; protocols; multilective computations; VLSI circuits

UR - http://eudml.org/doc/221992

ER -

## References

top- H. Abelson, Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158.
- N. Alon and W. Maas, Meanders, Ramsey theory and lower bounds for branching programs, in Proc.27th IEEE FOCS, IEEE (1986) 410-417.
- M. Ajtai, L. Babai, P. Hajnal, J. Komlós, P. Pudlák, V. Rödl, E. Szemerédi and G. Turán, Two lower bounds for branching programs, in Proc. 18th ACM STOC, ACM (1986) 30-38.
- A.V. Aho, J.D. Ullman and M. Yanakakis, On notions of information transfer in VLSI circuits, in Proc. 15th ACM STOC, ACM (1983) 133-139.
- L. Babai, N. Nisan and M. Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs. J. Comput. System Sci.45 (1992) 204-232.
- A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Computational Complexity3 (1993) 1-18.
- B. Bollig and I. Wegener, A very simple function that requires exponential size read-once branching programs. Inform. Process. Lett.66 (1998) 53-57.
- P. Duris and Z. Galil, On the power of multiple read in chip. Inform. and Comput.104 (1993) 277-287.
- P. Duris, and Galil Z., Schnitger G., Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91.
- M. Dietzfelbinger, J. Hromkovic and G. Schnitger, A comparison of two lower bounds methods for communication complexity. Theoret. Comput. Sci.168 (1996), 39-51.
- H.D. Gr÷ger, A new partition lemma for planar graphs and its application to circuit complexity, in Proc. FCT'91, Springer-Verlag, Lecture Notes in Computer Science529 (1991) 220-229.
- J. Hromkovic, M. Krause, Meinel and Ch., S. Waack, Branching programs provide lower bounds on the area of multilective deterministic and nondeterministic VLSI circuits. Inform. and Comput.95 (1992) 117-128.
- J. Hromkovic, Nonlinear lower bounds on the number of processors of circuits with sublinear seperators. Inform. and Comput.95 (1991) 117-128.
- J. Hromkovic, Communication Complexity and Parallel Computing. EATCS Series, Springer (1997).
- M. Krause, Lower bounds for depth-restricted branching programs. Inform. and Comput.91 (1991) 1-14.
- M. Krause, Ch. Meinel and S. Waack, Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines, in Proc. Structure in Complexity Theory (1989) 240-249.
- E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).
- R.J. Lipton and R.E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math.36 (1979) 177-189.
- E.A. Okolnishkova, On lower bounds for branching programs. Siberian Advances inMathematics3 (1993) 152-166.
- P. Pudlák and S. Zák, Space complexity of computation. Techn. Report, Prague (1983).
- M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115.
- J.E. Savage, The performance of multilective VLSI algorithms. J. Comput. System Sci.29 (1984) 243-273.
- J. Simon and M. Szegedy, A new lower bound theorem for read-only-once branching programs and its application, J. Cai, Ed., Advances in Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13, AMS (1993) 183-193.
- P. Savický and S. Zák, A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996).
- C.D. Thompson, Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88.
- Gy. Turán, On restricted Boolean circuits, in Proc. FCT'89, Springer-Verlag, Lecture Notes in Computer Science380 (1989) 460-469.
- Gy. Turán, Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett.30 (1989) 37-40.
- Gy. Turán, On the complexity of planar Boolean circuits. Comput. Complexity5 (1995) 24-42.
- J.D. Ullman, Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984).
- I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, John Wiley and Sons Ltd., and Teubner, B.G., Stuttgart (1987).
- I. Wegener, On the complexity of branching programs and decision trees for clique funcion. J. Assoc. Comput. Mach.35 (1988) 461-471.
- A.C. Yao, Some complexity questions related to distributive computing, in Proc. 11th ACM STOC, ACM (1979) 209-213.
- A.C. Yao, The entropic limitations on VLSI computations, in Proc. 11th ACM STOC, ACM (1979) 209-213.
- S. Zák, An exponential lower bound for one-time-only branching programs, in Proc MFCS '84, Springer, Berlin, Lecture Notes in Computer Science176 (1984) 562-566.
- S. Zák, An exponential lower bound for real-time branching programs. Inform. and Control71 (1986) 87-94.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.