Conference devoted to the 90th anniversary of Alexei A. Lyapunov

Akademgorodok, Novosibirsk, Russia, October 8-11, 2001,
(state registration number 0320300064)

Abstracts

Cybernetiks

Lower bounds on the complexity of branching programs

Okol'nishnikova E.A.

Sobolev Institute of Mathematics of Siberian Branch of Russian Academy of Sciences (Novosibirsk)

The problem of finding nontrivial lower bounds on the complexity of "well-defined" Boolean functions is one of the most important problems in the mathematical theory of complexity. In the paper the computation of characteristic functions of Reed-Muller codes by nondeterministic branching programs is considered.

Additional information: HTML
Note. Abstracts are published in author's edition

Comments

[Home]
[Conference]

©2001, Siberian Branch of Russian Academy of Science, Novosibirsk
©2001, United Institute of Computer Science SB RAS, Novosibirsk
©2001, Institute of Computational Techologies SB RAS, Novosibirsk
©2001, A.P. Ershov Institute of Informatics Systems SB RAS, Novosibirsk
©2001, Institute of Mathematics SB RAS, Novosibirsk
©2001, Institute of Cytology and Genetics SB RAS, Novosibirsk
©2001, Institute of Computational Mathematics and Mathematical Geophysics SB RAS, Novosibirsk
©2001, Novosibirsk State University
Last modified 06-Jul-2012 (11:45:21)