Charpin, Pascale

Crooked permutations were introduced twenty years ago since they allow to construct interesting objects in graph theory. The field of applications was extended later. Crooked functions, bijective or not, correspond to APN functions and to some optimal codes. We adopt an unified presentation of crooked functions, explaining the connection with parti...

Xu, Guoliang Qiu, Daowen
Published in
Quantum Information Processing

In quantum computation, designing an optimal exact quantum query algorithm (i.e., a quantum decision tree algorithm) for any small input Boolean function is a fundamental and abstract problem. As we are aware, there is not a general method for this problem. Due to the fact that every Boolean function can be represented by a sum-of-squares of some m...

Popkov, K. A.
Published in
Doklady Mathematics

AbstractWe introduce the concept of the uniform width of a contact circuit. For each Boolean function, we find the minimal possible value of the uniform width of a contact circuit implementing this function. We prove constructively that this value does not exceed 3. We also establish that, for almost all Boolean functions on n variables, it equals ...

Red’kin, N. P.
Published in
Mathematical Notes

Abstract For the monotone symmetric threshold Boolean functions \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$ f^n_2(\widetilde x\mspace{2mu})=\bigvee_{1\le i

Couceiro, Miguel Lehtonen, Erkko

In this paper we address the question "How many properties of Boolean functions can be defined by means of linear equations?" It follows from a result by Sparks that there are countably many such linearly definable classes of Boolean functions. In this paper, we refine this result by completely describing these classes. This work is tightly related...

Amarilli, Antoine Capelli, Florent Monet, Mikaël Senellart, Pierre
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 ...

Hao, Xuexuan Zhang, Fengrong Xia, Shixiong Zhou, Yong
Published in
Quantum Information Processing

Quantum algorithms for the analysis of Boolean functions have received a lot of attention over the last few years. The algebraic normal form (ANF) of a linear Boolean function can be recovered by using the Bernstein–Vazirani (BV) algorithm. No research has been carried out on quantum algorithms for learning the ANF of general Boolean functions. In ...

Logachev, Oleg A. Fedorov, Sergey N. Yashchenko, Valerii V.
Published in
Discrete Mathematics and Applications

A new equivalence relation on the set of Boolean functions is introduced: functions are declared to be Δ-equivalent if their autocorrelation functions are equal. It turns out that this classification agrees well with the cryptographic properties of Boolean functions: for functions belonging to the same Δ-equivalence class a number of their cryptogr...

Couceiro, Miguel Lehtonen, Erkko Mercuriali, Pierre Péchoux, Romain

A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as...

Redkin, Nikolay P.
Published in
Discrete Mathematics and Applications

We study generalized (in terms of bases) complexity of implementation of linear Boolean functions by Boolean circuits in arbitrary functionally complete bases; the complexity of a circuit is defined as the number of gates. Let L*(n) be the minimal number of gates sufficient for implementation of an arbitrary linear Boolean function of n variables i...