The More the Merrier: On Evolving Five-valued Spectra Boolean Functions

• URL: http://arxiv.org/abs/2411.12735v1
• Date: Tue, 19 Nov 2024 18:57:55 GMT
• Title: The More the Merrier: On Evolving Five-valued Spectra Boolean Functions
• Authors: Claude Carlet, Marko Ðurasevic, Domagoj Jakobovic, Luca Mariot, Stjepan Picek,
• Abstract summary: Evolving five-valued spectra Boolean functions with Walsh-Hadamard coefficients can only take five distinct values. We show that the tree encoding is superior to other choices, as we can obtain five-valued Boolean functions with high nonlinearity.
• Score: 32.90791284928444
• License:
• Abstract: Evolving Boolean functions with specific properties is an interesting optimization problem since, depending on the combination of properties and Boolean function size, the problem can range from very simple to (almost) impossible to solve. Moreover, some problems are more interesting as there may be only a few options for generating the required Boolean functions. This paper investigates one such problem: evolving five-valued spectra Boolean functions, which are the functions whose Walsh-Hadamard coefficients can only take five distinct values. We experimented with three solution encodings, two fitness functions, and 12 Boolean function sizes and showed that the tree encoding is superior to other choices, as we can obtain five-valued Boolean functions with high nonlinearity.

Related papers

• Degree is Important: On Evolving Homogeneous Boolean Functions [32.90791284928444]
  This paper investigates the use of Evolutionary Algorithms to design homogeneous bent Boolean functions. While EAs manage to find quadratic homogeneous bent functions, none of the approaches result in cubic homogeneous bent functions.
  arXiv  Detail & Related papers  (2025-01-30T15:04:14Z)
• 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)
• A New Angle: On Evolving Rotation Symmetric Boolean Functions [32.90791284928444]
  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.
  arXiv  Detail & Related papers  (2023-11-20T16:16:45Z)
• Non-Convex Bilevel Optimization with Time-Varying Objective Functions [57.299128109226025]
  We propose an online bilevel optimization where the functions can be time-varying and the agent continuously updates the decisions with online data. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions.
  arXiv  Detail & Related papers  (2023-08-07T06:27:57Z)
• 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)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• 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)
• Naive Feature Selection: a Nearly Tight Convex Relaxation for Sparse Naive Bayes [51.55826927508311]
  We propose a sparse version of naive Bayes, which can be used for feature selection. We prove that our convex relaxation bounds becomes tight as the marginal contribution of additional features decreases. Both binary and multinomial sparse models are solvable in time almost linear in problem size.
  arXiv  Detail & Related papers  (2019-05-23T19:30:51Z)

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.