This article is cited in 1 paper

Estimating the level of affinity of a quadratic form

A. V. Cheremushkin

Research Institute "Kvant"

Abstract: The level of affinity of a Boolean function is defined as the minimum number of variables such that assigning any particular values to these variables makes the function affine. The generalized level of affinity is defined as the minimum number of linear combinations of variables the values of which may be specified in such a way that the function becomes affine. For a quadratic form of rank $2r$ the generalized level of affinity is equal to $r$. We present some properties of the distribution of the rank of the random quadratic form and, as a corollary, derive an asymptotic estimate for the generalized level of affinity of quadratic forms.

Keywords: Boolean functions, quadratic forms, level of affinity.

UDC: 519.115+519.719.1

Received: 19.05.2016

DOI: 10.4213/dm1409

 English version: Discrete Mathematics and Applications, 2017, 27:6, 339–347

Bibliographic databases:

• 
• 
•