Bent functions and random Boolean formulas

DOI10.1016/0012-365X(94)00166-GMaRDI QIDQ1910518zbMATH OpenFDO

Authors Petr Savický

Publication date 24 March 1996

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)00166-G

zbMATH Keywords

bent functionsBoolean functions

Mathematics Subject Classification ID

Boolean functions (06E30) Linear codes (general theory) (94B05)

Review text

The author's previous three papers [Discrete Math. 83, 95--103 (1990; Zbl 0703.06006), Eur. J. Comb. 15, 407--410 (1994; Zbl 0797.94011), Comb. Probab. Comput. 7, No. 4, 451--463 (1998; Zbl 0927.68041)] are referred to and the degree of a connective is analysed. For asymptotic estimate of an arbitrary degree connective the Fourier transform is used. All the results of the paper are only asymptotic. It is proved, that the bent functions achieve asymptotically the minimal probability of occurring among all Boolean functions. At the same time, the linear functions achieve asymptotically the maximal probability. This paper presents 36 definitions, theorems and lemmas. It needs to be compared with the theory of Boolean functions [\textit{I. Wegener}, The complexity of Boolean functions. Stuttgart: B. G. Teubner (1987; Zbl 0623.94018)]. The bibliography contains 11 references.

Recommendations

• scientific article; zbMATH DE number 3974901
• scientific article; zbMATH DE number 4010400
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• On ``bent functions
• Asymptotic probability of values of random Boolean expressions

Cites work

• Complexity and Probability of Some Boolean Formulas
• Generating and counting binary bent sequences
• Harmonic Analysis of Polynomial Threshold Functions
• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 3763833 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 3318360 (Why is no real title available?)
• On ``bent functions
• On the bent Boolean functions that are symmetric
• Random Boolean formulas representing any Boolean function with asymptotically equal probability

Cited in

(1)

• scientific article; zbMATH DE number 4209213 (Why is no real title available?)

This page was built for publication: Bent functions and random Boolean formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1910518)