Lianna Hambardzumyan

activity

20152026

most citedFactorization norms and an inverse theorem for MaxCut

1 citations · 2 across the 10 of their papers we have counts for

collaborators

11 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…

math.CO2025★ 1 cited

Factorization norms and an inverse theorem for MaxCut

Igor Balla, Lianna Hambardzumyan, István Tomon

We prove that Boolean matrices with bounded $γ_{2}$ -norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hamba…

cs.CC2024

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 $B P P^{0}$ , does not contain a complete problem. In other words, there is…

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 $k$ players, each of whom can see every input but their own, if the $k$ input numbers add up to $N$ .…

cs.CC2022

On depth-3 circuits and covering number: an explicit counter-example

Lianna Hambardzumyan, Hamed Hatami, Ndiamé Ndiaye

We give a simple construction of $n \times n$ Boolean matrices with $Ω (n^{4/3})$ zero entries that are free of $2 \times 2$ all-zero submatrices and have covering number $O(\log^4(n…

cs.CC2021★ 1 cited

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…

cs.DM2020

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…

cs.DM2019

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 $O (\frac{n}{l o g n})$ players can bias the outcome of any Boolean function ${0, 1}^{n} \to {0, 1}$ with respe…

math.CO2017

Lower bounds for graph bootstrap percolation via properties of polynomials

Lianna Hambardzumyan, Hamed Hatami, Yingjie Qian

We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to determine the sizes…

cs.DM2015

Graphs, Disjoint Matchings and Some Inequalities

Lianna Hambardzumyan, Vahan Mkrtchyan

For $k \geq 1$ and a graph $G$ let $ν_{k} (G)$ denote the size of a maximum $k$ -edge-colorable subgraph of $G$ . Mkrtchyan, Petrosyan and Vardanyan proved that $ν_2(G)\geq \frac45\cdot…