close
Skip to main content
Springer Nature Link
Log in

Lower bounds for the majority communication complexity of various graph accessibility problems

  • Contributed Papers
  • Conference paper
  • First Online:
Save conference paper
View saved research
Mathematical Foundations of Computer Science 1995 (MFCS 1995)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 969))

  • 964 Accesses

  • 1 Citation

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. A. V. Aho, J. D. Ullman, M. Yannakakis, On notions of information transfer in VLSI circuits, in: Proc. 15th ACM STOC 1983, pp. 133–183.

    Google Scholar 

  2. L. Babai, P. Frankl, J. Simon, Complexity classes in communication complexity theory, in: Proc. 27th IEEE FOCS, pp. 337–347, 1986.

    Google Scholar 

  3. B. Halstenberg, R. Reischuk, Relations between Communication Complexity Classes, in: Proc. 3rd IEEE Structure in Complexity Theory Conference, pp. 19–28, 1988.

    Google Scholar 

  4. C. Damm, M. Krause, Ch. Meinel, St. Waack, Separating counting communication complexity classes, in: Proc. 9th STACS, Lecture Notes in Computer Science 577, Springer Verlag 1992, pp. 281–293.

    Google Scholar 

  5. A. Hajnal, W. Maass, G. Turan, On the communication complexity of graph problems, in: Proc. 20th ACM STOC 1988, pp. 186–191.

    Google Scholar 

  6. N. Immerman, Languages that capture complexity classes, SIAM J. Comput., 16(4)(1978), pp. 760–778.

    Article  Google Scholar 

  7. M. Krause, St. Waack, Variation ranks of communication matrices and lower bounds for depth two circuits having symmetric gates with unbounded fan-in, in: Proc. 32nd IEEE FOCS 1991, pp. 777–782.

    Google Scholar 

  8. Ch. Meinel, p-Projection reducibility and the complexity classes L(nonuniform) and NL(nonuniform), in: Proc. 12th MFCS, 1986, LNCS 233, 527–535.

    Google Scholar 

  9. Ch. Meinel, Modified branching programs and their computational power, LNCS 370, Springer-Verlag, 1989.

    Google Scholar 

  10. Ch. Meinel, St. Waack, Upper and lower bounds for certain graph-accessibility problems on bounded alternating Ω-branching programs, in: Complexity Theory — current research, Eds. K. Ambos-Spies, S. Homer, U. Schöming, Cambridge University Press 1993, 273–290.

    Google Scholar 

  11. Ch. Meinel, St. Waack, Lower Bounds on the Modular Communication Complexity of various graph-accessibility problems, in: Proc. LATIN'95, LNCS 911, 427–435.

    Google Scholar 

  12. K. Mehlhorn, E. M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing, in: Proc. 14th ACM STOC 1982, pp. 330–337.

    Google Scholar 

  13. R. Paturi, J. Simon, Probabilistic communication complexity, Journ. of Computer and System Science 33(1986), pp. 106–124.

    Google Scholar 

  14. R. Raz, B. Spieker, On the “log rank”-conjecture in communication complexity, in: Proc. 34th IEEE FOCS 1993, pp. 168–176.

    Google Scholar 

  15. W. Savitch, Relationship between nondeterministic and deterministic tape complexities, J. Comput. System Sci. 4(1970), pp. 244–253.

    Google Scholar 

  16. Skyum, L. V. Valiant, A complexity theory based on Boolean algebra, Proc., 22nd IEEE FOCS, pp. 244–253.

    Google Scholar 

  17. A. Yao, The entropie limitations of VLSI computations, Proc. 13th ACM STOC 1981, pp. 308–311.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Theoretische Informatik, Universität Trier, Fachbereich IV, D-54286, Trier

    Christoph Meinel

  2. Inst. für Num. und Angew. Mathematik, Univ. Göttingen, Lotzestr. 16-18, D-37083, Göttingen

    Stephan Waack

Authors
  1. Christoph Meinel
    View author publications

    Search author on:PubMed Google Scholar

  2. Stephan Waack
    View author publications

    Search author on:PubMed Google Scholar

Editor information

Jiří WiedermannPetr Hájek

Rights and permissions

Reprints and permissions

Copyright information

© 1995 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Meinel, C., Waack, S. (1995). Lower bounds for the majority communication complexity of various graph accessibility problems. In: Wiedermann, J., Hájek, P. (eds) Mathematical Foundations of Computer Science 1995. MFCS 1995. Lecture Notes in Computer Science, vol 969. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60246-1_136

Download citation

  • DOI: https://doi.org/10.1007/3-540-60246-1_136

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-60246-0

  • Online ISBN: 978-3-540-44768-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics