Asymptotically optimal Boolean functions

DOI10.1016/J.JCTA.2018.12.005MaRDI QIDQ1734702zbMATH OpenOpenAlexWikidataFDO

Authors Kai-Uwe Schmidt

Publication date 27 March 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.08215

zbMATH Keywords

Boolean functioncovering radiusnonlinearityReed-Muller code

Mathematics Subject Classification ID

Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75) Boolean functions (94D10)

Abstract: The largest Hamming distance between a Boolean function in $n$ variables and the set of all affine Boolean functions in $n$ variables is known as the covering radius $h{o}_n$ of the $[2^n,n+1]$ Reed-Muller code. This number determines how well Boolean functions can be approximated by linear Boolean functions. We prove that [ lim_{n oinfty}2^{n/2}- ho_n/2^{n/2-1}=1, ] which resolves a conjecture due to Patterson and Wiedemann from 1983.

Recommendations

• Theoretical upper bounds on the covering radii of Boolean functions
• On the approximation of a random Boolean function by the set of quadratic forms
• Nonlinearity of some invariant Boolean functions
• Highly nonlinear functions over finite fields
• On the Covering Radii of Binary Reed–Muller Codes in the Set of Resilient Boolean Functions

Cites work

• 9-variable Boolean functions with nonlinearity 242 in the generalized rotation symmetric class
• Bent functions. Fundamentals and results
• Calculation of certain Gauss sums
• Complete solving of explicit evaluation of Gauss sums in the index 2 case
• Covering radius of the Reed-Muller code \(R(1,7)\) -- a simpler proof
• scientific article; zbMATH DE number 5862915 (Why is no real title available?)
• scientific article; zbMATH DE number 1024657 (Why is no real title available?)
• scientific article; zbMATH DE number 1455087 (Why is no real title available?)
• Modifications of Patterson-Wiedemann functions for cryptographic applications
• Nonlinearity and propagation characteristics of balanced Boolean functions
• On ``bent functions
• On the covering radius of binary codes (Corresp.)
• Six Standard Deviations Suffice
• The covering radius of the (128,8) Reed-Muller code is 56 (Corresp.)
• The covering radius of the<tex>(2^{15}, 16)</tex>Reed-Muller code is at least 16276
• Weight distributions of the cosets of the (32,6) Reed-Muller code

Cited in

(14)

• Trading properties and Alexandrov kernels for Boolean functions
• Highly nonlinear functions over finite fields
• scientific article; zbMATH DE number 1866873 (Why is no real title available?)
• On the approximation of a random Boolean function by the set of quadratic forms
• On nonlinearity of Boolean functions generated by the generalized Dobbertin construction
• Mathematical Foundations of Computer Science 2004
• Modified Patterson-Wiedemann construction
• Spherical codes attached to complex weighing matrices
• Hadamard bent sequences and spherical designs
• On the vector subspaces of \(\mathbb{F}_{2^n}\) over which the multiplicative inverse function sums to zero
• A class of functions and their application in constructing semisymmetric designs
• Asymptotically minimal schemes for one sequence of Boolean functions
• Asymptotically best method for synthesis of Boolean recursive circuits
• Approximating Boolean functions by OBDDs

This page was built for publication: Asymptotically optimal Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1734702)