Content area

Abstract

Translate

An algorithm for computing the nonlinearity of a Boolean function from its algebraic normal form (ANF) is proposed. By generalizing the expression of the weight of a Boolean function in terms of its ANF coefficients, a formulation of the distances to linear functions is obtained. The special structure of these distances can be exploited to reduce the task of nonlinearity computation to solving an associated binary integer programming problem. The proposed algorithm can be used in cases where applying the Fast Walsh transform is infeasible, typically when the number of input variables exceeds 40.

Details

1009240
Subject
Mathematical programming;
Integer programming;
Algorithms;
Computation;
Boolean functions;
Boolean algebra;
Walsh transforms;
Weight;
Linear functions;
Nonlinearity
URL
http://arxiv.org/abs/1305.0860
Title
Nonlinearity Computation for Sparse Boolean Functions
Author
Çalık, Çağdaş
Publication title
arXiv.org; Ithaca
Publication year
2013
Publication date
May 3, 2013
Section
Computer Science; Mathematics
Publisher
Cornell University Library, arXiv.org
Source
arXiv.org
Place of publication
Ithaca
Country of publication
United States
University/institution
Cornell University Library arXiv.org
Publication subject
Biology, Statistics, Physics, Mathematics, Engineering--Electrical Engineering, Computers--Computer Engineering, Business And Economics--Banking And Finance
e-ISSN
2331-8422
Source type
Working Paper
Language of publication
English
Document type
Working Paper
Publication history
 
 
Online publication date
2013-05-07
Milestone dates
2013-05-03 (Submission v1)
Publication history
 
 
   First posting date
07 May 2013
ProQuest document ID
2085575609
Document URL
https://www.proquest.com/working-papers/nonlinearity-computation-sparse-boolean-functions/docview/2085575609/se-2?accountid=208611
Full text outside of ProQuest
http://arxiv.org/abs/1305.0860
Copyright
© 2013. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.
Last updated
2019-04-16
Database
ProQuest One Academic