Combinatorial method of polynomial expansion of symmetric Boolean functions

2013/06/24 by Danila Gorodecky, Danila A. Gorodecky, Gorodecky, Danila A.
Computer Science · Engineering · #Algorithms and Data Compression #Coding theory and cryptography #cs.DM #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1306.5568

12 pages, 4 figures, 1 table

arxiv created 2013/06/24 · arxiv updated 2013/06/25

Abstract

A novel polynomial expansion method of symmetric Boolean functions is described. The method is efficient for symmetric Boolean function with small set of valued numbers and has the linear complexity for elementary symmetric Boolean functions, while the complexity of the known methods for this class of functions is quadratic. The proposed method is based on the consequence of the combinatorial Lucas theorem.

Related

• Constructing and Counting Even-Variable Symmetric Boolean Functions with Algebraic Immunity not Less Than d
• Linear recurrences and asymptotic behavior of exponential sums of symmetric boolean functions
• On 2k-Variable Symmetric Boolean Functions with Maximum Algebraic Immunity k
• The new combinatorial identities of symmetric functions
• A Method for Fast Computing the Algebraic Degree of Boolean Functions