## Boolean constant degree functions on the slice are juntas

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...

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...

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...

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...

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 ...

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...

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.

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...

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...