CryptoDB
Best Quadratic Approximations of Cubic Boolean Functions
| Authors: | |
|---|---|
| Download: | |
| Abstract: | The problem of computing best low order approximations of Boolean functions is treated in this paper. We focus on the case of best quadratic approximations of a wide class of cubic functions of arbitrary number of variables, and provide formulas for their efficient calculation. Our methodology is developed upon Shannon's expansion formula and properties of best affine approximations of quadratic functions, for which we prove formulas for their direct computation, without use of the Walsh-Hadamard transform. The notion of nonquadricity is introduced, as the minimum distance from all quadratic functions, and cubic functions that achieve the maximum possible nonquadricity are determined, leading to a lower bound for the covering radius of second order Reed-Muller code $\mthf{R}(2,n)$ in $\mthf{R}(3,n)$. |
BibTeX
@misc{eprint-2007-13319,
title={Best Quadratic Approximations of Cubic Boolean Functions},
booktitle={IACR Eprint archive},
keywords={foundations / Bent functions; boolean functions; covering radius; lower order approximations; nonlinearity; nonquadricity; Reed-Muller codes.},
url={http://eprint.iacr.org/2007/037},
note={ nkolok@di.uoa.gr 13549 received 5 Feb 2007},
author={Nicholas Kolokotronis and Konstantinos Limniotis and Nicholas Kalouptsidis},
year=2007
}