Log-rank conjecture

Alice knows a row number and Bob knows a column number in the same table of zeros and ones. They want the entry where their choices meet, while sending as few bits as possible. Suppose four rows read 0,1; 0,1; 1,0; 1,0. Alice can send one bit telling Bob which of the two row patterns she has; he can read the entry and return its one-bit answer. The conjecture asks whether a different kind of simplicity—having few row patterns from which all the others can be made by weighted sums—always permits a short exchange. The number needed is called the table’s rank.[1] [2]

Alice receives a row index and Bob a column index of a shared table of zeros and ones, called a zero-one matrix. How many bits must they exchange to determine their selected entry exactly? A deterministic protocol fixes every message from the sender’s input and the messages so far. Its cost is the greatest number of bits exchanged over all input pairs. For the four-row example with rows 0,1; 0,1; 1,0; 1,0, the real rank is two: the two different rows are independent and span all four. Alice sends their one-bit type; Bob returns the one-bit entry. This gives a two-bit protocol in which both learn the answer, without claiming optimality.

Each completed transcript of an exact protocol describes a monochromatic rectangle: a set of row choices crossed with a set of column choices on which the answer is constant. A protocol of cost $c$ has at most $2^c$ completed transcripts. Its all-one rectangles each have rank at most one and sum to the matrix, so $\operatorname{rank}_{\mathbb R}M\le 2^c$. The conjecture asks for a converse at a larger scale: $D(M)\le C[\log_2(2+\operatorname{rank}_{\mathbb R}M)]^a$ for constants $C,a$ shared by all zero-one matrices. Here $D$ is minimum deterministic worst-case communication cost; adding two keeps the expression meaningful at small or zero rank.[1] [2]

Repeated rows make the example easy. A table can instead have many distinct rows that are weighted sums of just a few others, without an obvious way for Alice and Bob to use that fact. The missing guarantee must work for every table of zeros and ones, with an exact answer and no random choices in the protocol.[1]

The signed decompositions in the February 2026 revision allow rectangles to overlap and contributions to cancel. Turning this representation into a partition with few monochromatic rectangles, or into a comparably short protocol, is the missing step. The claim concerns real rank and exact deterministic communication; approximate-rank or randomized results must be connected to that exact deterministic real-rank target before they resolve it.[1] [2]

An algebraic description can combine numbers using both positive and negative weights. A message must instead tell its recipient something they can act on. Connecting these two forms of compression would explain when a compact description of shared data also makes a task cheap for people who each hold only part of its input.[1] [2]

A low-rank factorization says how rows are assembled, but it does not immediately tell Alice which message will let Bob evaluate his particular column. A protocol must organize every possible input pair into definite-answer regions. The problem therefore asks whether algebraic cancellation can always be converted into this organized exchange of information, linking linear algebra to the cost of distributed computation.[1] [2]