|
On the inheritance of properties of Boolean functions under restrictions
O. A. Logachev, A. A. Sal'nikov, V. V. Yashchenko
Abstract:
For a property $\mathcal P$ of Boolean functions, a Boolean function $f(x)$, $x\in V_n$, and a subspace $H$ of the space $V_n$ of all $n$-tuples of zeros and ones, we consider the set of all restrictions of the Boolean function $f(x)$ onto the cosets of $V_n$ with respect to $H$. If the function $f(x)$ itself and all its
$2^{n-\dim H}$ restrictions possess the property $\mathcal P$, we say that the property $\mathcal P$ is inherited under the restrictions of the Boolean function $f(x)$ and consider it as a new derived property.
In this paper, this approach is applied to the following property of Boolean functions:
the value $\hat f(\alpha)/2^n$, where $\hat f(\alpha)$ is the Walsh–Hadamard coefficient, is fixed;
the corresponding derived property is called the $(H,\alpha)$-stability.
We give convenient criteria for $(H,\alpha)$-stability in terms of zeros of the Walsh–Hadamard coefficients,
and establish relations between the $(H,\alpha)$-stability, correlation immunity, and $m$-resiliency.
This research was supported by the Russian Foundation for Basic Research,
grants 99–01–00929 and 99–01–00941.
Received: 02.07.2001 Revised: 11.04.2002
Citation:
O. A. Logachev, A. A. Sal'nikov, V. V. Yashchenko, “On the inheritance of properties of Boolean functions under restrictions”, Diskr. Mat., 14:2 (2002), 9–19; Discrete Math. Appl., 12:3 (2002), 201–212
Linking options:
https://www.mathnet.ru/eng/dm237https://doi.org/10.4213/dm237 https://www.mathnet.ru/eng/dm/v14/i2/p9
|
Statistics & downloads: |
Abstract page: | 613 | Full-text PDF : | 164 | References: | 51 | First page: | 1 |
|