RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1995 Volume 7, Issue 3, Pages 129–145 (Mi dm594)

This article is cited in 10 papers

О приближении случайной булевой функции множеством квадратичных форм

B. V. Ryazanov, S. I. Chechëta


Abstract: We consider the problem of approximation of a random Boolean function by elements of the set of all Boolean functions of degree no greater than two, i.e., by the quadratic forms. It is proved that the Hamming distance from a random Boolean function of $n$ variables to the set of all quadratic forms has in limit as $n\to\infty$ the double exponential distribution.

UDC: 519.1

Received: 09.07.1993


 English version:
Discrete Mathematics and Applications, 1995, 5:5, 473–489

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025