Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskretnaya Matematika, 2002, Volume 14, Issue 2, Pages 9–19
DOI: https://doi.org/10.4213/dm237
(Mi dm237)
 

On the inheritance of properties of Boolean functions under restrictions

O. A. Logachev, A. A. Sal'nikov, V. V. Yashchenko
References:
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
Bibliographic databases:
UDC: 519.7
Language: Russian
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
Citation in format AMSBIB
\Bibitem{LogSalYas02}
\by O.~A.~Logachev, A.~A.~Sal'nikov, V.~V.~Yashchenko
\paper On the inheritance of properties of Boolean functions under restrictions
\jour Diskr. Mat.
\yr 2002
\vol 14
\issue 2
\pages 9--19
\mathnet{http://mi.mathnet.ru/dm237}
\crossref{https://doi.org/10.4213/dm237}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1937004}
\zmath{https://zbmath.org/?q=an:1047.94009}
\transl
\jour Discrete Math. Appl.
\yr 2002
\vol 12
\issue 3
\pages 201--212
Linking options:
  • https://www.mathnet.ru/eng/dm237
  • https://doi.org/10.4213/dm237
  • https://www.mathnet.ru/eng/dm/v14/i2/p9
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Дискретная математика
    Statistics & downloads:
    Abstract page:613
    Full-text PDF :164
    References:51
    First page:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024