Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CROSS-INTERSECTING SET SYSTEMS:
Reports tagged with cross-intersecting set systems:
TR25-141 | 2nd October 2025
Lianna Hambardzumyan, Shachar Lovett, Morgan Shirley

The Log-Rank Conjecture: New Equivalent Formulations

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.

We propose a relaxed but still equivalent version of the conjecture based on a ... more >>>




ISSN 1433-8092 | Imprint