Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@InProceedings{carlet:2022:GECCO,

• author = "Claude Carlet and Marko Djurasevic and Domagoj Jakobovic and Luca Mariot and Stjepan Picek",
• title = "Evolving Constructions for Balanced, Highly Nonlinear Boolean Functions",
• booktitle = "Proceedings of the 2022 Genetic and Evolutionary Computation Conference",
• year = "2022",
• editor = "Alma Rahat and Jonathan Fieldsend and Markus Wagner and Sara Tari and Nelishia Pillay and Irene Moser and Aldeida Aleti and Ales Zamuda and Ahmed Kheiri and Erik Hemberg and Christopher Cleghorn and Chao-li Sun and Georgios Yannakakis and Nicolas Bredeche and Gabriela Ochoa and Bilel Derbel and Gisele L. Pappa and Sebastian Risi and Laetitia Jourdan and Hiroyuki Sato and Petr Posik and Ofer Shir and Renato Tinos and John Woodward and Malcolm Heywood and Elizabeth Wanner and Leonardo Trujillo and Domagoj Jakobovic and Risto Miikkulainen and Bing Xue and Aneta Neumann and Richard Allmendinger and Inmaculada Medina-Bulo and Slim Bechikh and Andrew M. Sutton and Pietro Simone Oliveto",
• pages = "1147--1155",
• address = "Boston, USA",
• series = "GECCO '22",
• month = "9-13 " # jul,
• organisation = "SIGEVO",
• publisher = "Association for Computing Machinery",
• publisher_address = "New York, NY, USA",
• keywords = "genetic algorithms, genetic programming, Boolean functions, evolutionary algorithms, non-linearity, secondary constructions, balancedness",
• isbn13 = "978-1-4503-9237-2",
• URL = "https://doi.org/10.1145/3512290.3528871",
• DOI = "doi:10.1145/3512290.3528871",
• video_url = "https://vimeo.com/725452312",
• abstract = "Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally.In this work, we ask whether genetic programming (GP) can evolve constructions resulting in balanced Boolean functions with high nonlinearity. This question is especially interesting as there are only a few known such constructions. Our results show that GP can find constructions that generalize well, i.e., result in the required functions for multiple tested sizes. Further, we show that GP evolves many equivalent constructions under different syntactic representations. Interestingly, the simplest solution found by GP is a particular case of the well-known indirect sum construction.",
• notes = "GECCO-2022 A Recombination of the 31st International Conference on Genetic Algorithms (ICGA) and the 27th Annual Genetic Programming Conference (GP)",

}

Genetic Programming entries for Claude Carlet Marko Durasevic Domagoj Jakobovic Luca Mariot Stjepan Picek

Citations