92 citations · 310 across the 34 of their papers we have counts for
46 papers
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…
Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
Andreas Björklund, Petteri Kaski, Tomohiro Koana +1
We show that sufficiently low tensor rank for the balanced tripartitioning tensor for a large enough constan…
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…
Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
Andreas Björklund, Radu Curticapean, Thore Husfeldt +2
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 [Pro…