Back to Search
Start Over
Nonlinearity measures of random Boolean functions
- Publication Year :
- 2013
-
Abstract
- The r-th order nonlinearity of a Boolean function is the minimum number of elements that have to be changed in its truth table to arrive at a Boolean function of degree at most r. It is shown that the (suitably normalised) r-th order nonlinearity of a random Boolean function converges strongly for all r\ge 1. This extends results by Rodier for r=1 and by Dib for r=2. The methods in the present paper are mostly of elementary combinatorial nature and also lead to simpler proofs in the cases that r=1 or 2.
- Subjects :
- Mathematics - Combinatorics
Computer Science - Information Theory
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1308.3112
- Document Type :
- Working Paper