1 citations · 1 across the 4 of their papers we have counts for
5 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…
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…
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…
Chang's lemma via Pinsker's inequality
Lianna Hambardzumyan, Yaqiao Li
Extending the idea in [Impagliazzo, R., Moore, C. and Russell, A., An entropic proof of Chang's inequality. SIAM Journal on Discrete Mathematics, 28(1), pp.173-176.] we give a shor…
Biasing Boolean Functions and Collective Coin-Flipping Protocols over Arbitrary Product Distributions
Yuval Filmus, Lianna Hambardzumyan, Hamed Hatami +2
The seminal result of Kahn, Kalai and Linial shows that a coalition of players can bias the outcome of any Boolean function with respe…