A New Angle: On Evolving Rotation Symmetric Boolean Functions

• URL: http://arxiv.org/abs/2311.11881v1
• Date: Mon, 20 Nov 2023 16:16:45 GMT
• Title: A New Angle: On Evolving Rotation Symmetric Boolean Functions
• Authors: Claude Carlet, Marko {\DH}urasevic, Bruno Ga\v{s}perov, Domagoj Jakobovic, Luca Mariot, Stjepan Picek
• Abstract summary: This paper uses several evolutionary algorithms to evolve rotation symmetric Boolean functions with different properties. Surprisingly, we find bitstring and floating point encodings work better than the tree encoding.
• Score: 32.90791284928444
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Rotation symmetric Boolean functions represent an interesting class of Boolean functions as they are relatively rare compared to general Boolean functions. At the same time, the functions in this class can have excellent properties, making them interesting for various practical applications. The usage of metaheuristics to construct rotation symmetric Boolean functions is a direction that has been explored for almost twenty years. Despite that, there are very few results considering evolutionary computation methods. This paper uses several evolutionary algorithms to evolve rotation symmetric Boolean functions with different properties. Despite using generic metaheuristics, we obtain results that are competitive with prior work relying on customized heuristics. Surprisingly, we find that bitstring and floating point encodings work better than the tree encoding. Moreover, evolving highly nonlinear general Boolean functions is easier than rotation symmetric ones.

Related papers

• A Systematic Evaluation of Evolving Highly Nonlinear Boolean Functions in Odd Sizes [35.305121158674964]
  We consider the problem of evolving highly nonlinear Boolean functions in odd sizes. Finding optimal solutions is impossible except for the smallest tested size. We find a Boolean function in nine inputs with nonlinearity 241.
  arXiv  Detail & Related papers  (2024-02-15T13:39:34Z)
• Look into the Mirror: Evolving Self-Dual Bent Boolean Functions [35.305121158674964]
  This paper experiments with evolutionary algorithms with the goal of evolving (anti-)self-dual bent Boolean functions. We successfully construct self-dual bent functions for each dimension. We also tried evolving secondary constructions for self-dual bent functions, but this direction provided no successful results.
  arXiv  Detail & Related papers  (2023-11-20T16:20:16Z)
• Going Beyond Neural Network Feature Similarity: The Network Feature Complexity and Its Interpretation Using Category Theory [64.06519549649495]
  We provide the definition of what we call functionally equivalent features. These features produce equivalent output under certain transformations. We propose an efficient algorithm named Iterative Feature Merging.
  arXiv  Detail & Related papers  (2023-10-10T16:27:12Z)
• Digging Deeper: Operator Analysis for Optimizing Nonlinearity of Boolean Functions [8.382710169577447]
  We investigate the effects of genetic operators for bit-string encoding in optimizing nonlinearity. By observing the range of possible changes an operator can provide, one can use this information to design a more effective combination of genetic operators.
  arXiv  Detail & Related papers  (2023-02-12T10:34:01Z)
• Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions [37.84234862910533]
  We show that genetic programming can evolve constructions resulting in balanced Boolean functions with high nonlinearity. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.
  arXiv  Detail & Related papers  (2022-02-17T16:33:24Z)
• Evolutionary Construction of Perfectly Balanced Boolean Functions [7.673465837624365]
  We investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy a property, perfect balancedness, along with a good nonlinearity profile. Surprisingly, the results show that GA with the weightwise balanced representation outperforms GP with the classical truth table phenotype in finding highly nonlinear WPB functions.
  arXiv  Detail & Related papers  (2022-02-16T18:03:04Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)
• Learning Set Functions that are Sparse in Non-Orthogonal Fourier Bases [73.53227696624306]
  We present a new family of algorithms for learning Fourier-sparse set functions. In contrast to other work that focused on the Walsh-Hadamard transform, our novel algorithms operate with recently introduced non-orthogonal Fourier transforms. We demonstrate effectiveness on several real-world applications.
  arXiv  Detail & Related papers  (2020-10-01T14:31:59Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)
• Space of Functions Computed by Deep-Layered Machines [74.13735716675987]
  We study the space of functions computed by random-layered machines, including deep neural networks and Boolean circuits. Investigating the distribution of Boolean functions computed on the recurrent and layer-dependent architectures, we find that it is the same in both models.
  arXiv  Detail & Related papers  (2020-04-19T18:31:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.