92 citations · 310 across the 34 of their papers we have counts for
9 papers · 1 filter
Partition Rank and Algebraic Circuit Lower Bounds
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.…
Optimal Union Probability Interval Is NP-Hard
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 probabilit…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…
A universal sequence of tensors for the asymptotic rank conjecture
Petteri Kaski, Mateusz Michałek
The exponent of a tensor over a field captures the base of the exponential growth rate of the tensor ra…
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 on points over a field of elements requires time unless the \#ETH-…
Tensor network complexity of multilinear maps
Per Austrin, Petteri Kaski, Kaie Kubjas
We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. These capture any algorithm based on low border rank tensor decompositions, such as $…