О рандомизированной сложности функций, аппроксимирующих функцию голосования

Рассматривается сложность реализации частичных булевых функций, приближающих булеву функцию от $n$ переменных, являющуюся булевой функцией голосования (по большинству) $M(x_1,\dots,x_n)$. Функции вычисляются на машине с произвольным доступом к памяти, снабженной генератором случайных чисел. Показано, что использование генераторов случайных чисел позволяет вычислять функции, грубо приближающие $M(x_1,\dots,x_n)$, за константное время. При вычислении функций, достаточно близких к $M(x_1,\dots,x_n)$, использование генераторов случайных чисел не позволяет более чем в константное число раз уменьшить сложность вычислений. Библиогр. 7.