Boolean functions--functions on the domain of the logical values “true” and “false”--represent a fundamental concept of computer science with applications in many areas, including the design of digital circuits, the specification and verification of hardware and software systems, cryptography, combinatorics, and discrete mathematics. This book presents contributions from the 2018 International Workshop on Boolean Problems, “a bi-annually held and well-established forum to discuss the recent advances on problems related to Boolean logic and Boolean algebra,” with a focus on both theoretical foundations and practical applications.

The first two chapters are derived from the workshop’s invited keynotes. First, Fey and Drechsler introduce and formalize an approach to “self-explaining” digital systems, where a digital system is enhanced by an additional layer for self-explanation based on an abstract model of the system. This layer registers occurrences of system events and the causal relationship of events with references to related parts of the specification of system requirements. A small robot controller case study illustrates the approach and how it supports users and designers in understanding the actions of the system by allowing them to reason about the constructed explanations.

Second, Oder et al. discuss lattice-based mechanisms for the secure implementation of cryptographic key exchange, which in contrast to existing approaches (based on prime factorization or discrete logarithms) cannot be attacked by quantum algorithms (according to the current state of knowledge). In particular, they discuss an approach based on the learning with errors (LWE) problem, that is, its variant ring-LWE that operates with polynomial rings over finite fields; the approach is implemented on an ARM processor, and its performance is experimentally evaluated. Both introductory chapters, while presenting novel research results, include ample background information, which makes them also usable as introductions to the fields.

The other nine chapters are “extended manuscripts based on the workshop handouts.” The first three papers cover a variety of topics: the extension of “the theory of derivative operations of the Boolean differential calculus to [new] classes of Boolean functions”; the algebraic properties of permutation matrices associated to “a special class of Boolean functions” called bent functions; and an analysis of the behaviors of various variants of Monte Carlo tree search for solving the Boolean satisfiability problem based on (aesthetically pleasing!) visualizations of the search trees.

The next three chapters focus on applications of logic synthesis: the automatic synthesis of Boolean expressions computing “majority decisions” by a novel algorithm that guarantees optimality of the results; the synthesis of target functions as regular switching lattices by heuristic algorithms that aim for minimal size; and the exact synthesis of exclusive-or sum-of-product (ESOP) representations of Boolean functions by an algorithm based on Boolean satisfiability.

The last three chapters again present different topics: an algorithm for the classification of Boolean functions according to varying criteria based on their transformation to the spectral domain; new results on reversible Boolean functions with the potential for application in the design of reversible circuits relevant in quantum computing; and, finally, the efficient combinatorial “hardware computation of modular multiplication and of the modulus function” with a detailed experimental evaluation.

By the nature of the book, as the presentation of novel research results, it is mainly addressed to experts in the field. Nevertheless, apart from the keynote contributions, many of the other papers contain ample introductions and background information to make the results accessible to researchers from other domains. The presentations have been carefully edited and typeset, often with well-designed and colorful diagrams that aid the study of the material. Thus, although not as a leisure activity, the book makes a good read for those who would like to learn about the state of the art in the theory and applications of Boolean functions.