UVictoria Discrete Math Seminar: Lianna Hambardzumyan

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 rank and partitioning number of a Boolean matrix are quasi-polynomially related.

In this talk, I will present a relaxed but still equivalent version of the conjecture based on a new matrix parameter, $\pm$-rank: the minimum number of all-1 rectangles needed to express the Boolean matrix as a $\pm 1$-sum. $\pm$-rank lies between rank and partition number, and our main result shows that it is in fact equivalent to rank up to a logarithmic factor.

This reframes the log-rank conjecture as: can every signed decomposition of a Boolean matrix be made positive with only quasi-polynomial blowup?

Additionally, I will show that the log-rank conjecture is equivalent to a conjecture on cross-intersecting set systems.

The talk is based on joint work with Shachar Lovett and Morgan Shirley.