Persons
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
 
Okolnishnikova, Elizaveta Antonovna

Statistics Math-Net.Ru
Total publications: 8
Scientific articles: 8

Number of views:
This page:419
Abstract pages:3377
Full texts:1781
References:194
Candidate of physico-mathematical sciences (1982)
Speciality: 01.01.09 (Discrete mathematics and mathematical cybernetics)
Keywords: complexity; circuit; Boolean function; bound; lower bound; branching program.
UDC: 519.174.2, 519.175.3, 519.714, 519.714.4, 519.725, 519.95
MSC: 68-XX, 94-XX, 05-XX

Subject:

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).

https://www.mathnet.ru/eng/person17580
List of publications on Google Scholar
List of publications on ZentralBlatt
https://mathscinet.ams.org/mathscinet/MRAuthorID/194064

Publications in Math-Net.Ru Citations
2011
1. E. A. Okolnishnikova, “On distributed circuits”, Diskretn. Anal. Issled. Oper., 18:6 (2011),  71–81  mathnet  mathscinet  zmath
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  mathnet  mathscinet  zmath; J. Appl. Industr. Math., 4:2 (2010), 231–235  scopus 3
2005
3. E. A. Okolnishnikova, “On the Number of Hamiltonian Cycles in Hamiltonian Dense Graphs”, Mat. Tr., 8:2 (2005),  199–206  mathnet  mathscinet; 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  mathnet  mathscinet 2
2001
5. 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  mathnet  mathscinet  zmath 4
2000
6. E. A. Okolnishnikova, “On two operations over Boolean functions”, Diskretn. Anal. Issled. Oper., Ser. 1, 7:1 (2000),  79–93  mathnet  mathscinet  zmath
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  mathnet  mathscinet  zmath
1995
8. E. A. Okolnishnikova, “On the comparison of the complexities of binary $k$-programs”, Diskretn. Anal. Issled. Oper., 2:4 (1995),  54–73  mathnet  mathscinet  zmath 2

Organisations
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024