R. G. Mubarakzjanov, “On the Complexity of Randomized Read-once Branching Programs”, Kazan. Gos. Univ. Uchen. Zap. Ser. Fiz.-Mat. Nauki, 2009, Volume 151, Book 2,Pages <nobr>107

The XV International Conference "Problems of Theoretical Cybernetics"

On the Complexity of Randomized Read-once Branching Programs

R. G. Mubarakzjanov

Kazan State University

Abstract: Ordered binary decision diagrams are a well known computational model. Graph-driven read-once branching programs presented in this paper generalize this model. Exponential lower bound of the complexity of such programs for integer multiplication is proven.

Keywords: Boolean function, binary branching program, complexity class, computation complexity lower bound.

UDC: 519.714

Received: 16.03.2009