On Some Bounds on the Size of Branching Programs (A Survey)
- 606 Downloads
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.
Unable to display preview. Download preview PDF.
- 5.Nečiporuk, E.: On a Boolean function. Soviet Math. Doklady 7, 999–1000 (1966)Google Scholar
- 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
- 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.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
- 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
- 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