1 citations · 2 across the 4 of their papers we have counts for
4 papers
Factorization norms and an inverse theorem for MaxCut
Igor Balla, Lianna Hambardzumyan, István Tomon
We prove that Boolean matrices with bounded -norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hamba…
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 .…
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…