You are looking at a specific version 20201023:084840 of this paper. See the latest version.

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 functionTotal InfluenceMonotone FunctionsBent FunctionsStrict Avalanche CriteriaPropagation CharacteristicPlateaued functionConstant Depth CircuitsLinear 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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.