Skip to main content
SpringerLink
Log in

Applications of matrix methods to the theory of lower bounds in computational complexity

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

We present some criteria for obtaining lower bounds for the formula size of Boolean functions. In the monotone case we get the boundn Ω(logn) for the function “MINIMUM COVER” using methods considerably simpler than all previously known. In the general case we are only able to prove that the criteria yield an exponential lower bound when applied to almost all functions. Some connections with graph complexity and communication complexity are also given.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. E. АНДРЕЕВ, ОБ ОДНОМ МЕтОДЕ пОлУЧЕНИь НИжНИх ОцЕНОк слОж НОстИ ИНДИВИДУАльН ых МОНОтОННых ФУНкцИИ — ДАН сссР,1985, т. 282, N5, 1033–1037. (Engl. transl. in:Sov. Math. Dokl. 31, 530–534.)

    Google Scholar 

  2. A. E. АНДРЕЕВ, ОБ ОДНОМ МЕтОДЕ пОлУЧЕНИь ЁФФЕктИВНых НИжНИх ОцЕНОк МОНОтОННОИ слОжНОстИ, АлгЕБРА И лОгИкА,1987, т. 26, 1, с. 3–26.

    Google Scholar 

  3. А. А. РАжБОРОВ, НИжНИЕ ОцЕНкИ МОНОтОННОИ слОжНОстИ НЕкОтОРых БУлЕВых ФУНкцИИ — ДАН сссР,1985, т. 281, N4, с. 798–801. (Engl. transl. in:Sov. Math. Dokl. 31, 354–357.)

    Google Scholar 

  4. А. А. РАжБОРОВ, НИжНИЕ ОцЕНкИ МОНОтОННОИ слОжНОстИ лОгИЧЕс кОгО пЕРМАНЕНтА — “МАтЕМ. жАМ.”,1985, т. 37, Вып. 6, с. 887–900. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 37, 485–493.)

    Google Scholar 

  5. А. А. РАжБОРОВ, НИж НИЕ ОцЕНкИ РАжМЕРА сх ЕМ ОгРАНИЧЕННОИ глУБИНы В пОлНОМ БАжИсЕ, сОДЕРжАЩЕМ ФУНкцИУ лОгИЧЕскОгО слОжЕНИь —МАтЕМ. жАМ.,1987, т. 41, Вып. 4, с. 598–607. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR. 41:4, 333–338.)

    Google Scholar 

  6. А. А.РАжБОРОВ, ФОРМУлы ОгРАНИЧЕННОИ глУБИНы В БАжИсЕ &, ⊕ И НЕкОтОРыЕ кОМБИНАтОРНыЕ жАДАЧИ — В сБ. «ВОпРОсы кИБЕРНЕтИкИ. слОж НОсть ВыЧИслЕНИИ И пРИклАДНАь МАтЕМАтИЧЕскАь лОг ИкА», М.:1988, с. 149–166.

  7. к. л.РыНкОВ, МОДИФИ кАцИь МЕтОДА В. М. хРАпЧЕНкО И пРИМЕНЕНИЕ ЕЕ к ОцЕНк АМ слОжНОстИ п-схЕМ Дль кОДОВых ФУНкцИИ — В сБ. «МЕтОДы ДИскРЕтНОгО АНАлИжА В тЕОРИИ гРАФОВ И схЕМ», Вып. 42, НОВОсИБИРск,1985, с. 91–98.

  8. В. М. хРАпЧЕНкО, О слОжНОстИ РЕАлИжАцИИ лИНЕИНОИ ФУНкцИИ В клАссЕ п-схЕМ,МАтЕМ. жАМ.,1971, т. 9, Вып. 1, с. 35–40. (Engl. transl. in:Mathem. Notes of the Academy of Sci. of the USSR 11 (1972), 474–479.)

    Google Scholar 

  9. A. V.Aho, J. D.Ullman, M.Yannakakis, On Notions of Information Transfer in VLSI Circuits —Proc. 15th ACM STOC,1983, 133–139.

  10. N. Alon, R. B. Boppana, The monotone circuit complexity of Boolean functions,Combinatorica,1987, v. 7, N1, 1–22.

    Google Scholar 

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

  12. A. Borodin, von zur Gathen, J. Hopcroft, Fast parallel matrix and GCD computations,Information and Control,52 (1982), 241–256.

    Google Scholar 

  13. B.Halsenberg, R.Reischuk, On Different Modes of Communication, 1988, 20th ACM STOC. 162–172.

  14. M.Karchmer, A.Wigderson, Monotone Circuits for Connectivity Require Super-logarithmic Depth,Proc. 20th ACM STOC,1988, 539–550.

  15. B. Lindström, H. O. Zetterström, A combinatorial problem in thek-adic number system,Proc. of the Amer. Math. Soc., 1967,18, 1, 166–170.

    Google Scholar 

  16. R. J.Lipton, R.Sedgewick, Lower Bounds for VLSI,Proc. 13th ACM STOC,1981, 300–307.

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

  18. P.Pudlak, V.Rödl,A combinatorial approach to complexity—unpublished manuscript,1989.

  19. P. Pudlak, V. Rödl, P. Savicky, Graph Complexity,Acta Informatica,25 (1988), 515–535.

    Google Scholar 

  20. P. M. Spira, On time-hardware complexity tradeoffs for Boolean functions,Proceedings of 4th Hawaii Symposium on System Sciences,1971, Western Periodicals Company, North Hollywood, 525–527.

    Google Scholar 

  21. é. Tardos, The gap between monotone and non-monotone circuit complexity is exponential,Combinatorica,1988, v. 8,1, 141–142.

    Google Scholar 

  22. I. Wegeher, Relating monotone formula size and monotone depth of Boolean functions,Information Processing Letters,16, (1983), 41–42.

    Google Scholar 

  23. A. C.Yao, Some Complexity Questions Related to Distributed Computing,Proc. 11th ACM STOC,1979, 209–213.

Download references

Author information

Authors and Affiliations

  1. Steklov Mathematical Institute, Vavilova 42, GSP-1, 117966, Moscow, USSR

    A. A. Razborov

Authors
  1. A. A. Razborov
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Razborov, A.A. Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10, 81–93 (1990). https://doi.org/10.1007/BF02122698

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02122698

AMS subject classification (1980)

Search

Navigation