2 papers
cs.CC2026
Spiky Rank and Its Applications to Rigidity and Circuits
Lianna Hambardzumyan, Konstantin Myasnikov, Artur Riazanov +2
We introduce spiky rank, a new matrix parameter that enhances blocky rank by combining the combinatorial structure of the latter with linear-algebraic flexibility. A spiky matrix i…
cs.CC2025
Sampling Permutations with Cell Probes is Hard
Yaroslav Alekseev, Mika Göös, Konstantin Myasnikov +2
Suppose we are given an infinite sequence of input cells, each initialized with a uniform random symbol from . How hard is it to output a sequence in that is close to…