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

Diskr. Mat., 2023 Volume 35, Issue 1, Pages 62–70 (Mi dm1756)

On the sets of the propagation criterion for strict majority Boolean functions

G. A. Isaev

Lomonosov Moscow State University

Abstract: In this paper we investigate the propagation criterion for strict majority symmetric Boolean functions. With the use of the theory of Krawtchouk polynomials it is shown that vectors whose Hamming weight differs from $n/2$ by at most $1/2$ satisfy the propagation criterion for strict majority functions in $n$ variables, where $\lfloor n/2\rfloor$ is odd.

Keywords: Boolean function, propagation criterion, symmetric Boolean function, strict majority Boolean function, Krawtchouk polynomial, Walsh spectrum.

UDC: 519.716.322+519.719.2

Received: 11.01.2023

DOI: 10.4213/dm1756


 English version:
Discrete Mathematics and Applications, 2025, 35:4, 227–233


© Steklov Math. Inst. of RAS, 2025