Boolean constant degree functions on the slice are juntas
Differential uniformity and the associated codes of cryptographic functions
The associated codes of almost perfect nonlinear (APN) functions have been widely studied. In this paper we consider more generally the codes associated with functions that have differential uniformity at least 4. We emphasize, for such a function F , the role of codewords of weight 3 and 4 and of some cosets of its associated code C F. We give som...
On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials
In this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equa-tional specification of median forms and extend it from the domain of monotone Boolean functions to the domain of polynomial functions over distributive lattices. This specification is sound and complete. We illustrate its use...
Recent Results on Constructing Boolean Functions with (Potentially) Optimal Algebraic Immunity Based on Decompositions o...
Published in Journal of Systems Science and Complexity
Boolean functions with optimal algebraic immunity (OAI functions) are important cryptographic primitives in the design of stream ciphers. During the past decade, a lot of work has been done on constructing such functions, among which mathematics, especially finite fields, play an important role. Notably, the approach based on decompositions of addi...
Boolean functions as points on the hypersphere in the Euclidean space
Published in Discrete Mathematics and Applications
A new approach to the study of algebraic, combinatorial, and cryptographic properties of Boolean functions is proposed. New relations between functions have been revealed by consideration of an injective mapping of the set of Boolean functions onto the sphere in a Euclidean space. Moreover, under this mapping some classes of functions have extremel...
Connecting Knowledge Compilation Classes Width Parameters
Published in Theory of Computing Systems
The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width ...
On the Minimization of Boolean Functions for Additive Complexity Measures
Published in Journal of Applied and Industrial Mathematics
The problem of minimizing Boolean functions for additive complexity measures in a geometric interpretation, as covering a subset of vertices in the unit cube by faces, is a special type of a combinatorial statement of the weighted problem of a minimal covering of a set. Its specificity is determined by the family of covering subsets, the faces of t...
Tests Concerning Certain Types of Faults at the Scheme Inputs
Published in Moscow University Computational Mathematics and Cybernetics
Estimates are obtained for the Shannon function of the length of a diagnostic test with respect to cyclic shifts of scheme inputs, and for the Shannon function of fault detection and length of a diagnostic test with respect to a single stuck-at fault and a cyclic shift of scheme inputs.
Limit Points of Bernoulli Distribution Algebras Induced by Boolean Functions
Published in Lobachevskii Journal of Mathematics
We consider Bernoulli distribution algebras, i.e. sets of distributions that are closed under transformations achieved by substituting independent random variables for arguments of Boolean functions from a given system. We establish that, unless the transforming set contains only essentially unary functions, the set of algebra limit points is eithe...
On the Perfectness of Minimal Regular Partitions of the Edge Set of the n-Dimensional Cube
Published in Journal of Applied and Industrial Mathematics
We prove that, for n equal to 3, 5, and a power of 2, every minimal partition of the edge set of the n-dimensional cube is perfect. As a consequence, we obtain some description of the classes of all minimal parallel-serial contact schemes (π-schemes) realizing the linear Boolean functions that depend essentially on n variables for the corresponding...
