Welcome to the resource topic for 2007/037
Title:
Best Quadratic Approximations of Cubic Boolean Functions
Authors: Nicholas Kolokotronis, Konstantinos Limniotis, Nicholas Kalouptsidis
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).
ePrint: https://eprint.iacr.org/2007/037
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .