Petteri Kaski

SODA Conference 2025 Conference Paper

Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture

• Andreas Björklund
• Radu Curticapean
• Thore Husfeldt
• Petteri Kaski
• Kevin Pratt

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n -vertex graph can be computed deterministically in O (1. 99982 n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2 n poly( n ) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2 n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting k -colorings for small k and enumerating k -colorable subgraphs, with an extension and derandomisation of Pratt’s tensor-based algorithm for balanced three-way partitioning to the unbalanced case.

STOC Conference 2024 Conference Paper

The Asymptotic Rank Conjecture and the Set Cover Conjecture Are Not Both True

• Andreas Björklund
• Petteri Kaski

Strassen’s asymptotic rank conjecture [ Progr. ‍Math. ‍120 ‍(1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any є>0 there exists a positive integer constant k such that no algorithm solves the k -Set Cover problem in worst-case time ((2−є) n | F |poly( n )). The k -Set Cover problem asks, given as input an n -element universe U , a family F of size-at-most- k subsets of U , and a positive integer t , whether there is a subfamily of at most t sets in F whose union is U . The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh ‍in the monograph Parameterized Algorithms [Springer, ‍2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlstr'om ‍[CCC ‍2012, ACM ‍Trans. ‍Algorithms ‍2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS ‍2019], in this scenario we would also get an ((2−δ) n )-time randomized algorithm for some constant δ>0 for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given n -vertex directed graph has a Hamiltonian cycle. At a fine-grained level, our results do not need the full strength of the asymptotic rank conjecture; it suffices that the conclusion of the conjecture holds approximately for a single 7× 7× 7 tensor.

STOC Conference 2022 Conference Paper

The shortest even cycle problem is tractable

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski

NeurIPS Conference 2022 Conference Paper

Trustworthy Monte Carlo

• Juha Harviainen
• Mikko Koivisto
• Petteri Kaski

Monte Carlo integration is a key technique for designing randomized approximation schemes for counting problems, with applications, e. g. , in machine learning and statistical physics. The technique typically enables massively parallel computation, however, with the risk that some of the delegated computations contain spontaneous or adversarial errors. We present an orchestration of the computations such that the outcome is accompanied with a proof of correctness that can be verified with substantially less computational resources than it takes to run the computations from scratch with state-of-the-art algorithms. Specifically, we adopt an algebraic proof system developed in computational complexity theory, in which the proof is represented by a polynomial; evaluating the polynomial at a random point amounts to a verification of the proof with probabilistic guarantees. We give examples of known Monte Carlo estimators that admit verifiable extensions with moderate computational overhead: for the permanent of zero--one matrices, for the model count of disjunctive normal form formulas, and for the gradient of logistic regression models. We also discuss the prospects and challenges of engineering efficient verifiable approximation schemes more generally.

SODA Conference 2021 Conference Paper

The Fine-Grained Complexity of Computing the Tutte Polynomial of a Linear Matroid

• Andreas Björklund
• Petteri Kaski

We show that computing the Tutte polynomial of a linear matroid of dimension k on k O (1) points over a field of k O (1) elements requires k Ω( k ) time unless the #ETH—a counting extension of the Exponential Time Hypothesis of Impagliazzo and Paturi [CCC 1999] due to Dell et al. [ACM TALG 2014]—is false. This holds also for linear matroids that admit a representation where every point is associated to a vector with at most two nonzero coordinates. Moreover, we also show that the same is true for computing the Tutte polynomial of a binary matroid of dimension k on k O (1) points with at most three nonzero coordinates in each point's vector. These two results stand in sharp contrast to computing the Tutte polynomial of a k -vertex graph (that is, the Tutte polynomial of a graphic matroid of dimension k —which is representable in dimension k over the binary field so that every vector has exactly two nonzero coordinates), which is known to be computable in 2 k k O (1) time [Björklund et al. , FOCS 2008]. Our lower-bound proofs proceed in three steps: 1. a classic connection due to Crapo and Rota [1970] between the number of tuples of codewords of full support and the Tutte polynomial of the matroid associated with the code; 2. an earlier-established #ETH-hardness of counting the solutions to a bipartite ( d, 2)-CSP on n vertices in d o ( n ) time; and 3. new embeddings of such CSP instances as questions about codewords of full support in a linear code. Geometrically, our hardness results also establish that it is #ETH-hard to compute the volume of proper hyperplane chambers in time k o ( k ) for a given arrangement of hyperplanes through the origin of a finite k -dimensional vector space over a k O (1) -element field. We complement these lower bounds with two algorithm designs to form essentially a complexity dichotomy under #ETH. The first design computes the Tutte polynomial of a linear matroid of dimension k on k O (1) points in k O ( k ) arithmetic operations in the base field. The second design generalizes the Björklund et al. algorithm from the graphic case and runs in q k +1 k O (1) time for linear matroids of dimension k defined over the q -element field by k O (1) points with at most two nonzero coordinates each.

AAAI Conference 2020 Conference Paper

Error-Correcting and Verifiable Parallel Inference in Graphical Models

• Negin Karimi
• Petteri Kaski
• Mikko Koivisto

We present a novel framework for parallel exact inference in graphical models. Our framework supports error-correction during inference and enables fast verification that the result of inference is correct, with probabilistic soundness. The computational complexity of inference essentially matches the cost of w-cutset conditioning, a known generalization of Pearl’s classical loop-cutset conditioning for inference. Verifying the result for correctness can be done with as little as essentially the square root of the cost of inference. Our main technical contribution amounts to designing a low-degree polynomial extension of the cutset approach, and then reducing to a univariate polynomial employing techniques recently developed for noninteractive probabilistic proof systems.

SODA Conference 2019 Conference Paper

Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication

• Matti Karppa
• Petteri Kaski

We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable improvements over their deterministic counterparts for specific tensors of interest, starting from the tensor 〈2, 2, 2〉 that represents 2 × 2 matrix multiplication. While it is well known that the (deterministic) tensor rank and border rank satisfy [V. Strassen, Numer. Math. 13 (1969); J. E. Hopcroft and L. R. Kerr, SIAM J. Appl. Math. 20 (1971); S. Winograd, Linear Algebra Appl. 4 (1971); J. M. Landsberg, J. AMS 19 (2006)], we show that the probabilistic tensor rank and border rank satisfy By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles in graphs. Our algorithms are opportunistic in the sense that their worst-case scaling is essentially governed by the probabilistic rank, yet their result is accumulated through independent repetitions, where the partial result can be inspected at each repeat for possible early termination, and each repeat scales according to the rank of the outcome-tensors. For example, representing 〈2, 2, 2〉 probabilistically using an ensemble of tensors of rank 6, we obtain an algorithm that, with high probability, multiplies two 2 d × 2 d Boolean matrices in operations. This algorithm consists of independent repeats that each run in O (6 d ) operations and enable inspection of the partial result at each repeat. Analogously, a probabilistic representation of 〈2, 2, 2〉 using tensors of border rank 5 gives an algorithm that runs in operations, consisting of repeats that run in Õ (5 d ) operations each. Asymptotically, we use Adleman's argument to show that, over the complex field, the support rank exponent ω s of matrix multiplication [H. Cohn and C. Umans, SODA ’12] gives the lower bound for probabilistic tensor rank. While this enables an approach to obtaining asymptotically faster algorithm designs for matrix multiplication via the Cohn–Umans inequality, the main motivation for the present paper is to enable an approach towards fast practical algorithms using small probabilistic tensors.

SAT Conference 2017 Conference Paper

An Adaptive Prefix-Assignment Technique for Symmetry Reduction

• Tommi A. Junttila
• Matti Karppa
• Petteri Kaski
• Jukka Kohonen

Abstract 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) parallelisability—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 tentative practical applicability of our technique we have prepared a preliminary implementation and report on a limited set of experiments that demonstrate ability to reduce symmetry on hard instances.

SODA Conference 2016 Conference Paper

A Faster Subquadratic Algorithm for Finding Outlier Correlations

• Matti Karppa
• Petteri Kaski
• Jukka Kohonen

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 < τ < ρ < 1. Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({–1, 1}-valued data normalized to unit Euclidean length) runs in time where 0 < γ < 1 is a constant tradeoff parameter and M ( μ, v ) is the exponent to multiply an ⌊ n μ ⌋ × ⌊ n v ⌋ matrix with an ⌊ n v ⌋ × ⌊ n μ ⌋ matrix and Δ = 1/(1 – log τ ρ ). As corollaries we obtain randomized algorithms that run in time and in time where 2 ≤ ω < 2. 38 is the exponent for square matrix multiplication and 0. 3 < α ≤ 1 is the exponent for rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation Õ (·) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ.)

SODA Conference 2014 Conference Paper

Counting Thin Subgraphs via Packings Faster Than Meet-in-the-Middle Time

• Andreas Björklund
• Petteri Kaski
• Lukasz Kowalik

Vassilevska and Williams (STOC 2009) showed how to count simple paths on k vertices and matchings on k /2 edges in an n -vertex graph in time n k /2+ O (1). In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP 2009), and Björklund et al. (ESA 2009), via n st /2+ O (1) -time algorithms for counting t -tuples of pairwise disjoint sets drawn from a given family of s -sized subsets of an n -element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have Ω( n ⌊ st /2⌋ ) and Ω( n ⌊ k /2⌋ ) lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the “meet-in-the-middle” exponent st /2 can be beaten and give an algorithm that counts in time n 0. 4547 st + O (1) for t a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on k vertices and pathwidth p ≪ k in an n -vertex graph in n 0. 4547 k +2 p + O (1) time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound.

SODA Conference 2012 Conference Paper

Fast zeta transforms for lattices with few irreducibles

• Andreas Björklund
• Mikko Koivisto
• Thore Husfeldt
• Jesper Nederlof
• Petteri Kaski
• Pekka Parviainen

SAT Conference 2012 Conference Paper

Finding Efficient Circuits for Ensemble Computation

• Matti Järvisalo
• Petteri Kaski
• Mikko Koivisto
• Janne H. Korhonen

Abstract Given a Boolean function as input, a fundamental problem is to find a Boolean circuit with the least number of elementary gates (AND, OR, NOT) that computes the function. The problem generalises naturally to the setting of multiple Boolean functions: find the smallest Boolean circuit that computes all the functions simultaneously. We study an NP-complete variant of this problem titled Ensemble Computation and, especially, its relationship to the Boolean satisfiability (SAT) problem from both the theoretical and practical perspectives, under the two monotone circuit classes: OR-circuits and SUM-circuits. Our main result relates the existence of nontrivial algorithms for CNF-SAT with the problem of rewriting in subquadratic time a given OR-circuit to a SUM-circuit. Furthermore, by developing a SAT encoding for the ensemble computation problem and by employing state-of-the-art SAT solvers, we search for concrete instances that would witness a substantial separation between the size of optimal OR-circuits and optimal SUM-circuits. Our encoding allows for exhaustively checking all small witness candidates. Searching over larger witness candidates presents an interesting challenge for current SAT solver technology.

FOCS Conference 2008 Conference Paper

Computing the Tutte Polynomial in Vertex-Exponential Time

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski
• Mikko Koivisto

The deletion–contraction algorithm is perhapsthe most popular method for computing a host of fundamental graph invariants such as the chromatic, flow, and reliability polynomials in graph theory, the Jones polynomial of an alternating link in knot theory, and the partition functions of the models of Ising, Potts, and Fortuin–Kasteleyn in statistical physics. Prior to this work, deletion–contraction was also the fastest known general-purpose algorithm for these invariants, running in time roughly proportional to the number of spanning trees in the input graph. Here, we give a substantially faster algorithm that computes the Tutte polynomial—and hence, all the aforementioned invariants and more—of an arbitrary graph in time within a polynomial factor of the number of connected vertex sets. The algorithm actually evaluates a multivariate generalization of the Tutte polynomial by making use of an identity due to Fortuin and Kasteleyn. We also provide a polynomial-space variant of the algorithm and give an analogous result for Chung and Graham's cover polynomial.

STOC Conference 2007 Conference Paper

Fourier meets möbius: fast subset convolution

• Andreas Björklund
• Thore Husfeldt
• Petteri Kaski
• Mikko Koivisto

We present a fast algorithm for the subset convolution problem:given functions f and g defined on the lattice of subsets of an n -element set n , compute their subset convolution f*g, defined for S⊆ N by [ (f * g)(S) = [T ⊆ S] f(T) g(S/T),]where addition and multiplication is carried out in an arbitrary ring. Via Möbius transform and inversion, our algorithm evaluates the subset convolution in O(n 2 2 n ) additions and multiplications, substanti y improving upon the straightforward O(3 n ) algorithm. Specifically, if the input functions have aninteger range [-M,-M+1,...,M], their subset convolution over the ordinary sum--product ring can be computed in Õ(2 n log M) time; the notation Õ suppresses polylogarithmic factors.Furthermore, using a standard embedding technique we can compute the subset convolution over the max--sum or min--sum semiring in Õ(2 n M) time. To demonstrate the applicability of fast subset convolution, wepresent the first Õ(2 k n 2 + n m) algorithm for the Steiner tree problem in graphs with n vertices, k terminals, and m edges with bounded integer weights, improving upon the Õ(3 k n + 2 k n 2 + n m) time bound of the classical Dreyfus-Wagner algorithm. We also discuss extensions to recent Õ(2 n )-time algorithms for covering and partitioning problems (Björklund and Husfeldt, FOCS 2006; Koivisto, FOCS 2006).

TCS Journal 2005 Journal Article

Exact and approximate balanced data gathering in energy-constrained sensor networks

• Patrik Floréen
• Petteri Kaski
• Jukka Kohonen
• Pekka Orponen