RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Diskretn. Anal. Issled. Oper.: Year: Volume: Issue: Page: Find

 Diskretn. Anal. Issled. Oper., Ser. 1, 2001, Volume 8, Number 1, Pages 77–93 (Mi da216)

On the randomized complexity of functions that approximate a voting function

A. V. Chashkin

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: We consider the complexity of the realization of partial Boolean functions that approximate a Boolean function of $n$ variables, which is the Boolean voting function (by majority) $M(x_1,…,x_n)$. The functions are computed on a computer with arbitrary memory capacity and equipped with a random number generator. We show that the use of random number generators allows us to compute functions that roughly approximate $M(x_1,…,x_n)$ in constant time. In computing functions that are sufficiently close to $M(x_1,…,x_n)$ the use of random number generators does not allow the complexity of computation to be lowered more than a constant number of times.

Full text: PDF file (1233 kB)

Bibliographic databases:
UDC: 519.7

Citation: A. V. Chashkin, “On the randomized complexity of functions that approximate a voting function”, Diskretn. Anal. Issled. Oper., Ser. 1, 8:1 (2001), 77–93

Citation in format AMSBIB
\Bibitem{Cha01}
\by A.~V.~Chashkin
\paper On the randomized complexity of functions that approximate a~voting function
\jour Diskretn. Anal. Issled. Oper., Ser.~1
\yr 2001
\vol 8
\issue 1
\pages 77--93
\mathnet{http://mi.mathnet.ru/da216}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=1846865}
\zmath{https://zbmath.org/?q=an:0973.68078}