Name
Title | ||
|---|---|---|
An Upper Bound on the Number of Iterations for Transforming a Boolean Function of Degree Greater or Equal Than 4 to a Function of Degree 3 |
Abstract | ||
|---|---|---|
The difficulty involved in characterizing the weight distribution of all Boolean functions of degree {\geq} 3 is well-known [2, p. 446]. In [1] the author introduces a transformation on Boolean functions which changes their weights in a way that is easy to follow, and which, when iterated, reduces the degree of the function to 2 or 3. He concludes that it is just as difficult to characterize the weight of any function of degree 3 as it is for any other degree. The application of this transformation on a Boolean function defined on V_m = GF(2)^m, m \in \Bbb{N}, increases the number of its variables by two. On the other hand, in order to reduce the degree of a function to 2 or 3 it is necessary to apply the tranformation a number of times that grows exponentially with respect to m. In this paper, a factorization method on Boolean functions that allows the establishment of an upper bound for the number of applications of the transformation is presented. It shows that, in general, it is possible to significantly decrease the number of iterations in this process of degree reduction. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1023/A:1011279406162 | Des. Codes Cryptography |
Keywords | Field | DocType |
Boolean functions,Hamming weight | Maximum satisfiability problem,Boolean function,Discrete mathematics,Combinatorics,Upper and lower bounds,Parity function,Complexity index,Weight distribution,Hamming weight,Iterated function,Mathematics | Journal |
Volume | Issue | ISSN |
24 | 3 | 1573-7586 |
Citations | PageRank | References |
0 | 0.34 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. Tapia-Recillas | 1 | 12 | 3.88 |
| G. Vega | 2 | 5 | 1.22 |