The so-called “basic algorithm” of pseudo-Boolean programming is due to Hammer, Rosenberg and Rudeanu (1963). It allows to minimize nonlinear 0-1 polynomials by recursive elimination of one variable at each iteration. This algorithm was revisited by Crama, Hansen and Jaumard (1990) who showed that is has linear-time complexity when applied to functions associated in a natural way with graphs of bounded treewidth. In Clausen, Crama, Lusby, Rodriguez-Heck and Ropke (2023), we have again taken a new look at this old algorithm. We have shown that it can be efficiently implemented on instances associated with graphs of small “reach” (or bandwidth). On a set of publicly available instances of the low autocorrelation binary sequence problem, a notoriously hard pseudo-Boolean programming problem, we demonstrate the efficiency of the approach by showing that this specialized version of the basic algorithm solves to optimality several previously unsolved instances.

The well-known monotone Boolean dualization (MBD) problem calls for finding the irredundant DNF corresponding to a given monotone CNF. It is known that the problem is polynomially equivalent to that of enumerating all maximal feasible solutions for a given system of knapsack inequalities. In this talk, we consider the extension to chance-constrained knapsack inequalities and give sufficient conditions under which the enumeration problem remains polynomially reducible to MBD. In particular, we show that all maximal feasible solutions for a chance-constrained knapsack inequality can be enumerated in quasi-polynomial time when the item sizes are normally distributed and the covariance matrix has constant cp-rank. Whether or not the rank restriction can be dropped remains an interesting open question.

A monotone Boolean function is threshold if its sets of true points and false points can be separated by a linear inequality. The recognition problem for monotone threshold Boolean functions given by an irredundant DNF is known to be solvable in polynomial time using linear programming; however, no 'purely combinatorial' algorithm is known. In this talk we will discuss a subclass of monotone threshold Boolean functions called 1-Sperner Boolean functions, for which we prove a structural decomposition theorem. Some applications to graphs will also be outlined, including new characterizations of threshold graphs and new classes of graphs of bounded clique-width.

In this talk, we study the succinctness of various Boolean ML models. To be more precise, the existence of polynomial-time and polynomial-space translations between representation languages for binary classifiers is investigated. The languages that are considered include decision trees, random forests, several types of boosted trees, binary neural networks, Boolean multilayer perceptrons, and various logical representations of binary classifiers. We provide a complete map indicating for every pair of languages whether or not a polynomial-time / polynomial-space translation exists from one to the other.

In this talk, we introduce a subclass of hypergraph Horn functions that we call matroid Horn functions. We overview the characterizations of matroid Horn functions in terms of their canonical and complete CNF representations. Then we study the Boolean minimization problem for this class, where the goal is to find a minimum size representation of a matroid Horn function given by a CNF representation. While there are various ways to measure the size of a CNF, we focus on the number of circuits and circuit clauses. We determine the size of an optimal representation for binary matroids and give lower and upper bounds in the uniform case. For uniform matroids, we show a strong connection between our problem and Turán systems that might be of independent combinatorial interest.

Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These functions play a fundamental role in algebra, artificial intelligence, combinatorics, computer science, database theory, and logic. In the present paper, we introduce the subclass of hypergraph Horn functions that generalizes matroids and equivalence relations. We provide multiple characterizations of hypergraph Horn functions in terms of implicate-duality and the closure operator, which are respectively regarded as generalizations of matroid duality and Mac Lane—Steinitz exchange property of matroid closure. We also study algorithmic issues on hypergraph Horn functions, and show that the recognition problem (i.e., deciding if a given definite Horn CNF represents a hypergraph Horn function) and key realization (i.e., deciding if a given hypergraph is realized as a key set by a hypergraph Horn function) can be done in polynomial time, while implicate sets can be generated with polynomial delay.

Given a representation of Boolean function \(f\) in language \(L\), Boolean minimization is the task of finding the smallest representation of \(f\) in language \(L\). This task is computationally hard in most standard knowledge representation languages. In this talk we will concentrate mostly on CNF minimization (i.e. we will consider the language of all CNFs as both the source and target language) and review a long history of results on this topic, in particular for the subclass of Horn CNFs. We will also touch on the minimization problem in a less standard language when Horn clauses are clustered as linked lists in a directed hypergraph.

I’ll give examples of recent results in the area of promise constraint satisfaction problems.

A binary constraint tree (BCT, Wang and Yap 2022) is a normalized binary CSP whose constraint graph is a tree. A BCT constraint is a constraint represented with a BCT where some of the variables may be hidden (i.e. existentially quantified and used only for internal representation). Structured decomposable negation normal forms (SDNNF) were introduced by Pipatsrisawat and Darwiche (2008) as a restriction of decomposable negation normal forms (DNNF). Both DNNFs and SDNNFs were studied in the area of knowledge compilation. In this paper we show that the BCT constraints are polynomially equivalent to SDNNFs. In particular, a BCT constraint can be represented with an SDNNF of polynomial size and, on the other hand, a constraint that can be represented with an SDNNF, can be represented as a BCT constraint of polynomial size. This generalizes the result of Wang and Yap (2022) that shows that a multivalued decision diagram (MDD) can be represented with a BCT. Moreover, our result provides a full characterization of binary constraint trees using a language that is well studied in the area of knowledge compilation. It was shown by Wang and Yap (2023) that a CSP on \(n\) variables of domain sizes bounded by \(d\) that has treewidth \(k\) can be encoded as a BCT on \(O(n)\) variables with domain sizes \(O(d^{k+1})\). We provide an alternative reduction for the case of binary CSPs. This allows us to compile any binary CSP to an SDNNF of size that is parameterized by \(d\) and \(k\).

Two CNF formulas are called ucp-equivalent, if they behave in the same way with respect to unit clause propagation (ucp). A formula is called ucp-irredundant, if removing any clause leads to a formula which is not ucp-equivalent to the original one. The ratio of the size of a ucp-irredundant formula and the size of a minimal ucp-equivalent formula is at most \(n^2\), where \(n\) is the number of the variables. This upper bound is probably not tight, however, proving a better upper bound is an open problem. We demonstrate that a general upper bound on the above ratio cannot be smaller than \(\Omega(n/\ln n)\) using an example based on a ucp-irredundant propagation complete formula for a symmetric definite Horn function.

In this talk, we give an overview of some of the applications of Boolean functions in symmetric cryptography, and some of the most important properties that they must satisfy in order to provide secure encryption, such as balancedness, nonlinearity and algebraic degree. We present arguably the two most important representations of Boolean functions in cryptography, namely the algebraic normal form (ANF) and the univariate polynomial representation. We survey the main notions of equivalence that are used to classify cryptographic Boolean functions, and we briefly outline the major research directions.