Separation Results for Boolean Function Classes

Aniruddha Biswas; Palash Sarkar

Paper 2020/1324

Separation Results for Boolean Function Classes

Aniruddha Biswas and Palash Sarkar

Abstract

We show (almost) separation between certain important classes of Boolean functions. The technique that we use is to show that the total influence of functions in one class is less than the total influence of functions in the other class. In particular, we show (almost) separation of several classes of Boolean functions which have been studied in the coding theory and cryptography from classes which have been studied in combinatorics and complexity theory.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Boolean function Total Influence Monotone Functions Bent Functions Strict Avalanche Criteria Propagation Characteristic Plateaued function Constant Depth Circuits Linear Threshold Function
Contact author(s): anib_r @ isical ac in
aniruddhabiswas535 @ gmail com
palash @ isical ac in
History: 2020-10-23: received
Short URL: https://ia.cr/2020/1324
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1324,
      author = {Aniruddha Biswas and Palash Sarkar},
      title = {Separation Results for Boolean Function Classes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1324},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1324}
}