Communication Complexity and Lower Bounds on Multilective Computations

Juraj Hromkovič

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

top
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 < 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.

How to cite

top

Hromkovič, 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
  1. H. Abelson, Lower bounds on information transfer in distributed computations, in Proc. 19th IEEE FOCS, IEEE (1978) 151-158.  
  2. N. Alon and W. Maas, Meanders, Ramsey theory and lower bounds for branching programs, in Proc.27th IEEE FOCS, IEEE (1986) 410-417.  
  3. 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.  
  4. 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.  
  5. 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.  
  6. A. Borodin, A. Razborov and R. Smolensky, On lower bounds for read-k-times branching programs. Computational Complexity3 (1993) 1-18.  
  7. B. Bollig and I. Wegener, A very simple function that requires exponential size read-once branching programs. Inform. Process. Lett.66 (1998) 53-57.  
  8. P. Duris and Z. Galil, On the power of multiple read in chip. Inform. and Comput.104 (1993) 277-287.  
  9. P. Duris, and Galil Z., Schnitger G., Lower bounds on communication complexity, in Proc. 16th ACM STOC, ACM (1984), 81-91.  
  10. M. Dietzfelbinger, J. Hromkovic and G. Schnitger, A comparison of two lower bounds methods for communication complexity. Theoret. Comput. Sci.168 (1996), 39-51.  
  11. 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.  
  12. 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.  
  13. J. Hromkovic, Nonlinear lower bounds on the number of processors of circuits with sublinear seperators. Inform. and Comput.95 (1991) 117-128.  
  14. J. Hromkovic, Communication Complexity and Parallel Computing. EATCS Series, Springer (1997).  
  15. M. Krause, Lower bounds for depth-restricted branching programs. Inform. and Comput.91 (1991) 1-14.  
  16. 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.  
  17. E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).  
  18. R.J. Lipton and R.E. Tarjan, A separator theorem for planar graphs. SIAM J. Appl. Math.36 (1979) 177-189.  
  19. E.A. Okolnishkova, On lower bounds for branching programs. Siberian Advances inMathematics3 (1993) 152-166.  
  20. P. Pudlák and S. Zák, Space complexity of computation. Techn. Report, Prague (1983).  
  21. M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. STACS'98, Lecture Notes in Computer Science (1373) 105-115.  
  22. J.E. Savage, The performance of multilective VLSI algorithms. J. Comput. System Sci.29 (1984) 243-273.  
  23. 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.  
  24. P. Savický and S. Zák, A large lower bound for 1-branching programs. ECCC Report TR D36-96 (1996).  
  25. C.D. Thompson, Area-time complexity for VLSI, in Proc. 11th ACM STOC, ACM (1979) 81-88.  
  26. Gy. Turán, On restricted Boolean circuits, in Proc. FCT'89, Springer-Verlag, Lecture Notes in Computer Science380 (1989) 460-469.  
  27. Gy. Turán, Lower bounds for synchronous circuits and planar circuits. Inform. Process. Lett.30 (1989) 37-40.  
  28. Gy. Turán, On the complexity of planar Boolean circuits. Comput. Complexity5 (1995) 24-42.  
  29. J.D. Ullman, Computational Aspects of VLSI. Comput. Science Press, Rockwille MD (1984).  
  30. I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science, John Wiley and Sons Ltd., and Teubner, B.G., Stuttgart (1987).  
  31. I. Wegener, On the complexity of branching programs and decision trees for clique funcion. J. Assoc. Comput. Mach.35 (1988) 461-471.  
  32. A.C. Yao, Some complexity questions related to distributive computing, in Proc. 11th ACM STOC, ACM (1979) 209-213.  
  33. A.C. Yao, The entropic limitations on VLSI computations, in Proc. 11th ACM STOC, ACM (1979) 209-213.  
  34. 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.  
  35. S. Zák, An exponential lower bound for real-time branching programs. Inform. and Control71 (1986) 87-94.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.