RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2017 Number 5, Pages 51–55 (Mi vmumm96)

Short notes

Incomparable integrals and approximate calculation of monotone Boolean functions

A. V. Chashkin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The number of incomparable $k$-dimensional intervals in the Boolean $n$-cube is estimated. The result is used to estimate the complexity of approximate computation of an arbitrary monotone Boolean function of $n$ variables.

Key words: monotone Boolean function, complexity of approximate computation, incomparable intervals.

UDC: 519.7

Received: 12.10.2016


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2017, 72:5, 206–209

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024