RECORD
A Search for Nonlinear Balanced Boolean Functions by Leveraging Phenotypic Properties
Neural and Evolutionary Computing · Submitted 15 Jun 2023
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The results reveal promising convergence speed improvements for Boolean functions of sizes $N=6$ to $N=9$.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting coding theory. We provide an approach for finding such functions by a local search method that exploits the structure of the underlying problem. Previous attempts in this vein typically focused on using the properties of the fitness landscape to guide the search. We opt for a different path in which we leverage the phenotype landscape (the mapping from genotypes to phenotypes) instead. In the context of the underlying problem, the phenotypes are represented by Walsh-Hadamard spectra of the candidate solutions (Boolean functions). We propose a novel selection criterion, under which the phenotypes are compared directly, and test whether its use increases the convergence speed (measured by the number of required spectra calculations) when compared to a competitive fitness function used in the literature. The results reveal promising convergence speed improvements for Boolean functions of sizes $N=6$ to $N=9$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. | background 0.96 | 0.29 | 0.03 | asserted 0.74 |
| s1 | Such functions have extensive applications in domains such as cryptography and error-correcting coding theory. | background 1.00 | 0.04 | 0.02 | asserted 1.00 |
| s2 | We provide an approach for finding such functions by a local search method that exploits the structure of the underlying problem. | method 0.64 | 0.91 | 0.05 | asserted 1.00 |
| s3 | Previous attempts in this vein typically focused on using the properties of the fitness landscape to guide the search. | background 0.96 | 0.03 | 0.02 | asserted 0.99 |
| s4 | We opt for a different path in which we leverage the phenotype landscape (the mapping from genotypes to phenotypes) instead. | contribution 0.64 | 0.79 | 0.04 | asserted 0.97 |
| s5 | In the context of the underlying problem, the phenotypes are represented by Walsh-Hadamard spectra of the candidate solutions (Boolean functions). | method 0.91 | 0.30 | 0.02 | asserted 1.00 |
| s6 | We propose a novel selection criterion, under which the phenotypes are compared directly, and test whether its use increases the convergence speed (measured by the number of required spectra calculations) when compared to a competitive fitness function used in the literature. | contribution 0.63 | 0.93 | 0.09 | hedged possibility 0.39 |
| s7 | The results reveal promising convergence speed improvements for Boolean functions of sizes $N=6$ to $N=9$. | result 1.00 | 0.96 | 0.79 | asserted 0.62 |
What was examined, and what was not
- arXiv listing abstract v1
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
In this paper, we consider the problem of finding perfectly balanced Boolean functions with high non-linearity values. Such functions have extensive applications in domains such as cryptography and error-correcting coding theory. We provide an approach for finding such functions by a local search method that exploits the structure of the underlying problem. Previous attempts in this vein typically focused on using the properties of the fitness landscape to guide the search. We opt for a different path in which we leverage the phenotype landscape (the mapping from genotypes to phenotypes) instead. In the context of the underlying problem, the phenotypes are represented by Walsh-Hadamard spectra of the candidate solutions (Boolean functions). We propose a novel selection criterion, under which the phenotypes are compared directly, and test whether its use increases the convergence speed (measured by the number of required spectra calculations) when compared to a competitive fitness function used in the literature. The results reveal promising convergence speed improvements for Boolean functions of sizes $N=6$ to $N=9$.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
What it cites · 8 sentences without a confident label
Cites as background 2 papers
-
Some researchers, like Manzoni et al. [ref] , incorporated different local search methods into metaheuristics to improve and study the resulting convergence speed and diversity.
The Influence of Local Search over Genetic Algorithms with Balanced Representations · Related work · 0.80
-
There is a rich history of work in finding highly non-linear Boolean functions via metaheuristics [ref] , starting with Millan et. al.
A Survey of Metaheuristic Algorithms for the Design of Cryptographic Boolean Functions · Related work · 0.99
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.