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.
Biography
Graduated from Faculty of Mathematics and Mechanics of Novosibirsk State University in 1970 (department of theoretical cybernetics). Ph.D. thesis was defended in 1982. A list of my works contains more than 30 titles.
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).
E. A. Okolnishnikova, “On distributed circuits”, Diskretn. Anal. Issled. Oper., 18:6 (2011), 71–81
2009
2.
E. A. Okolnishnikova, “Lower bound for the computation complexity of BCH-codes for branching programs”, Diskretn. Anal. Issled. Oper., 16:5 (2009), 69–77; J. Appl. Industr. Math., 4:2 (2010), 231–235
E. A. Okolnishnikova, “On the Number of Hamiltonian Cycles in Hamiltonian Dense Graphs”, Mat. Tr., 8:2 (2005), 199–206; Siberian Adv. Math., 16:4 (2006), 79–85
2003
4.
E. A. Okolnishnikova, “On the complexity of nondeterministic branching programs that realize characteristic functions of Reed–Muller codes”, Diskretn. Anal. Issled. Oper., Ser. 1, 10:3 (2003), 67–81
E. A. Okolnishnikova, “On a method for obtaining lower bounds for the complexity of the realization of Boolean functions by nondeterministic branching programs”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:4 (2001), 76–102
E. A. Okolnishnikova, “On two operations over Boolean functions”, Diskretn. Anal. Issled. Oper., Ser. 1, 7:1 (2000), 79–93
1999
7.
E. A. Okolnishnikova, “Comparison of the complexities of nondeterministic branching $k$-programs”, Diskretn. Anal. Issled. Oper., Ser. 1, 6:1 (1999), 65–85
1995
8.
E. A. Okolnishnikova, “On the comparison of the complexities of binary $k$-programs”, Diskretn. Anal. Issled. Oper., 2:4 (1995), 54–73
Contact us: