Advertisement

On Some Bounds on the Size of Branching Programs (A Survey)

  • Elizaveta A. Okol’nishnikova
Conference paper
  • 606 Downloads
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)

Abstract

Previously it was shown by the author that it is possible to reduce obtaining of lower bounds on the complexity of Boolean functions for branching programs without restriction to obtaining of lower bounds on the complexity of minorants of the considered function for branching programs with restriction on the number of occurrences of a variable in a path (read-k-times branching programs). Theorems that reduce the problem of nonlinear lower bounds on the complexity of Boolean functions for branching programs to the problem of lower bounds on the complexity of covering of the set of “ones” of a Boolean function by functions of the defined type or to the problem of obtaining the upper bounds on the number of “ones” of a Boolean function in i-faces of a cube of the defined dimension are presented. A survey of bounds obtained by this method is given.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    Babai, L., Pudlák, P., Rödl, V., Szemerédi, M.: Lower bounds to the complexity of symmetric Boolean functions. Theoretical Computer Science 74, 313–324 (1990)zbMATHCrossRefMathSciNetGoogle Scholar
  2. 2.
    Bollig, B., Sauerhoff, M., Wegener, I.: On the nonappoximability on boolean functions by OBDD and read-k-times branching programs. Information and Computation 178, 263–278 (2002)zbMATHMathSciNetGoogle Scholar
  3. 3.
    Borodin, A., Razborov, A., Smolensky, R.: On lower bounds for read-k-times branching programs. Computational Complexity 3(1), 1–18 (1993)zbMATHCrossRefMathSciNetGoogle Scholar
  4. 4.
    MacWilliams, F.J., Sloane, N.J.F.: The theory of Error-Correcting Codes. North-Holland, Amsterdam (1977)zbMATHGoogle Scholar
  5. 5.
    Nečiporuk, E.: On a Boolean function. Soviet Math. Doklady 7, 999–1000 (1966)Google Scholar
  6. 6.
    Okol’nishnikova, E.A.: Lower bounds on complexity for the realization of characteristic functions of binary codes by binary programs. Metody Diskret. Anal. 51, 61–83 (1991) (in Russian) (see also: Siberian Adv. Math., 3(1), 152–166) (1993)Google Scholar
  7. 7.
    Okol’nishnikova, E.A.: On the hierarchy of nondeterministic branching k-programs. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol. 1279, pp. 376–387. Springer, Heidelberg (1997)CrossRefGoogle Scholar
  8. 8.
    Okol’nishnikova, E.A.: On one method of obtaining of lower bounds of Boolean functions for nondeterministic branching programs. Diskretn. Anal. Issled. Oper. Ser. 1 8(4), 76–102 (2001) (in Russian) (see also: ECCC TR02-020,2002), available at http://www.eccc.uni-tri.de/eccc/ (in English)
  9. 9.
    Okol’nishnikova, E.A.: On the complexity of nondeterministic branching programs for characteristic functions of Reed–Muller codes. Diskretn. Anal. Issled. Oper. Ser. 1 10(3), 67–81 (2003) (in Russian) Google Scholar
  10. 10.
    Pudlák, P.: A lower bound on complexity of branching programs. In: Chytil, M.P., Koubek, V. (eds.) MFCS 1984. LNCS, vol. 176, pp. 480–489. Springer, Heidelberg (1984)CrossRefGoogle Scholar
  11. 11.
    Pudlák, P.: The hierarchy of Boolean circuits. Comput. Artificial Intelligence 6(5), 449–468 (1987)zbMATHMathSciNetGoogle Scholar
  12. 12.
    Razborov, A.A.: Lower bounds on the complexity of symmetric Boolean functions by switching-rectifier circuits. Matemat. zametki 48(6), 79–90 (1990)zbMATHMathSciNetGoogle Scholar
  13. 13.
    Razborov, A.A.: Lower bounds for deterministic and nondeterministic branching program. In: Budach, L. (ed.) FCT 1991. LNCS, vol. 529, pp. 47–61. Springer, Heidelberg (1991)Google Scholar
  14. 14.
    Sauerhoff, M.: Randomness versus nondeterminism for read-once and read-k branching programs. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol. 1373, pp. 105–115. Springer, Heidelberg (1998)CrossRefGoogle Scholar
  15. 15.
    Sauerhoff, M.: Randomness versus nondeterminism for read-once and read-k branching programs. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 307–318. Springer, Heidelberg (2003)CrossRefGoogle Scholar
  16. 16.
    Thathachar, J.S.: On separating the read-k-times program hierarchy. In: Proc. of the 30th annual ACM Symposium on theory of computing, pp. 652–662 (1998)Google Scholar
  17. 17.
    Wei, V.K.: Generalized Hamming weights for linear codes. IEEE Trans. on Inform. Theory 37(5), 1412–1418 (1991)zbMATHCrossRefGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Elizaveta A. Okol’nishnikova
    • 1
  1. 1.Sobolev Institute of Mathematics of Siberian Branch of Russian Academy of SciencesNovosibirskRussia

Personalised recommendations