Main scientific interest is the theory of complexity. Some lower bounds on the complexity of Boolean functions for different circuits are obtained. The computation of monotone Boolean functions with formulas in the complete basis $(\vee,\&,\neg)$ and the monotone basis $(\vee,\&) is considered. It is shown that the use of negations can essentially diminish the complexity of monotone functions for formulas. A method of obtaining lower bounds on the complexity of Boolean functions for branching programs is suggested. Nonlinear lower bounds on the complexity of characteristic functions of Reed–Muller codes and BCH-codes for nondeterministic and deterministic branching programs are obtained. Lower bounds for circuits with restrictions are essentially used for obtaining lower bounds for circuits without restrictions. Some results on the complexity of Boolean functions for circuits with restrictions are obtained. The concept of monotone extension was introduced. It is shown that the operations of geometrical projection and monotone extension of Boolean functions can increase the complexity of Boolean functions for some classes of circuits. The connection between these two concepts is established.
Main publications:
Okol'nishnikova E. A. On the role of negations in the computation of monotome Boolean functions by formulas in the basis (V,&,-) // Discrete analysis. V. 33. - 1979. - P. 68–76.
Okol'nishnikova E. A. Lower bounds on branching programs // Siberian Adv. Math. - 1993. - V. 3, N 1. - P. 152–166.
Okol'nishnikova E. A. On one method of obtaining lower bounds on the complexity of Boolean functions for nondeterministic branching programs // Disrete analysis and operation research - 2001. - Т. 8, N 4. - P. 76–102.
Okol'nishnikova E. A. On the hierarchy of nondeterministic branching $k$-programs // Fundamentals of computation theory. 11th International symposium, FCT 97 (Krakow, September 1–3, 1997). - Proc. Berlin: Springer, 1997. - P. 376–387 (Lecture Notes in Computer Science. - V. 1279).
Okol'nishnikova E. A. On some bounds on the size of branching programs (a survey) // 3rd Symposium on Stochastic Algorithms, Foundations and Applications, SAGA2005) (Moscou, October 20–22, 2005). - Proc. Berlin: Springer, 2005. (Lecture Notes in Computer Science. - V. 3777. - P. 107–115).
