Mia Persson

collaborators

2 papers

cs.DS2023

$(min, +)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences

Andrzej Lingas, Mia Persson

We study the time complexity of computing the $(min, +)$ matrix product of two $n \times n$ integer matrices in terms of $n$ and the number of monotone subsequences the rows of the…

cs.CC2023

Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits

Andrzej Lingas, Mia Persson

A monotone Boolean circuit is composed of OR gates, AND gates and input gates corresponding to the input variables and the Boolean constants. It is $q$ -multilinear if for each its…

(min,+) Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences

Improved Lower Bounds for Monotone q-Multilinear Boolean Circuits

$(min, +)$ Matrix and Vector Products for Inputs Decomposable into Few Monotone Subsequences