4 papers
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…
A Study of the Binary and Boolean Rank of Matrices with Small Constant Real Rank
Michal Parnas, Adi Shraibman
We initiate the study of the binary and Boolean rank of matrices that have a small rank over the reals. The relationship between these three rank functions is an important op…
The Rank-Ramsey Problem and the Log-Rank Conjecture
Gal Beniamini, Nati Linial, Adi Shraibman
A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our…
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 .…