4 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 r…