3 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
The Log-Rank Conjecture: New Equivalent Formulations
Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley
The log-rank conjecture is a longstanding open problem with multiple equivalent formulations in complexity theory and mathematics. In its linear-algebraic form, it asserts that the…
cs.CC2023
An improved protocol for ExactlyN with more than 3 players
Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif +2
The ExactlyN problem in the number-on-forehead (NOF) communication setting asks players, each of whom can see every input but their own, if the input numbers add up to .…