Petteri Kaski

Petteri Kaski, Heikki Mannila, Chandra Kanta Mohapatra

A problem dating back to Boole [Laws of Thought, Walton & Maberly,1854] is what can be computed about the probability of a finite union of events when given as input the probabilities of intersections of some of the events. The modern geometric study of the problem can be traced back to Hailperin [Amer. Math. Monthly 2 (1965) 343--359] who phrased the problem in the language of linear programming and generalized it to logical formulas of the events other than disjunction, heralding a substantial body of work in probabilistic logic [Nilsson, Artif.\ Intell.\ 28 (1986) 71--87], including the probabilistic satisfiability problem of Georgakopoulos, Kavvadis, and Papadimitriou [J.Complexity 4 (1988) 1--11], as well as fundamental connections to the geometry of metrics via cut and correlation polytopes [Deza and Laurent, Geometry of Cuts and Metrics, Springer, 1997] and to the study of marginal polytopes in graphical models of machine learning [Wainwright and Jordan, Found.\ Trends Mach.\ Learn. 1 (2008) 1--305]. This paper (i) describes the pertinent geometry of Boole's problem via coordinate projections of an elementary polytope arising essentially from Hailperin's linear program on the atoms of a Venn diagram, and (ii) shows that computing the optimal interval for the union probability is NP-hard, resolving an apparent gap in the literature highlighted by Pitowsky [Math.\ Programming 50 (1991) 395--414] and Boros et al. [Math.\ Oper.\ Res. 39 (2014) 1311--1329 and 51 (2026) 134--148].

Tommi Junttila, Matti Karppa, Petteri Kaski et al.

This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework [J.~Algorithms 26 (1998), no.~2, 306--324]. Among key features of the technique are (i) adaptability---the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability---prefix-assignments can be processed in parallel independently of each other; (iii) versatility---the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability---the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.

Cornelius Brand, Petteri Kaski, Jiaheng Wang

Strassen's theory of bilinear complexity provides a mathematical characterization of the arithmetic complexity of primitives such as matrix multiplication via the rank of tensors. However, the connection to tensor rank is known to break down in higher degrees of multilinearity. In this work, we highlight an unexplored connection between a generalized notion of tensor rank, which can be defined in Naslund's framework of partition ranks (JCTA 2020), and multiplicative complexity. These partition ranks allow us to control the multiplicative complexity, and thus arithmetic complexity, in any constant degree of multilinearity from below, while recovering Strassen's seminal characterization in the bilinear case. This enables novel potential applications of the rank-based approaches to problems in fine-grained algorithms and complexity, such as the hyperclique conjecture of Lincoln-Williams-Vassilevska Williams (SODA 2018). Moreover, we exhibit connections to established notions of rank, such as tensor slice rank (in the sense of Tao and Sawin), as well as its symmetric variant. For computing the latter symmetric variant, we point out a simple NP-hardness proof, contrasting the rather involved NP-hardness proof for ordinary, non-symmetric tensor slice rank by Bläser et al. (SODA 2021).