1 citations · 2 across the 8 of their papers we have counts for
6 papers · 1 filter
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…
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…
No Complete Problem for Constant-Cost Randomized Communication
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms +1
We prove that the class of communication problems with public-coin randomized constant-cost protocols, called , does not contain a complete problem. In other words, there is…
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 .…
On depth-3 circuits and covering number: an explicit counter-example
Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye
We give a simple construction of Boolean matrices with zero entries that are free of all-zero submatrices and have covering number $O(\log^4(n…
A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
Lianna Hambardzumyan, Hamed Hatami, Pooya Hatami
We refute the Probabilistic Universal Graph Conjecture of Harms, Wild, and Zamaraev, which states that a hereditary graph property admits a constant-size probabilistic universal gr…