gpt 6 astra pro attempt on CS-24

The Log-Rank Conjecture

Definitions and mathematical statement

For $f:X\times Y\to\{-1,1\}$, Alice knows $x$, Bob knows $y$, and $D(f)$ is the minimum worst-case number of communicated bits in a deterministic protocol computing $f(x,y)$. Its sign matrix is $M_f=(f(x,y))$. The conjecture is \[ \exists C\ge1\ \forall f:\qquad D(f)\le C\left(\log_2\max\{2,\operatorname{rank}_{{\mathbb{R}}}M_f\}\right)^C. \] The same constant works for all nonempty finite $X,Y$. The rank is over ${\mathbb{R}}$; it is not Boolean rank or nonnegative rank, and the communication is deterministic.

Formulation and concept references: [S1].

Short English statement

Is deterministic communication complexity always bounded by a fixed power of the logarithm of the sign matrix's real rank?

Research attempt

Current frontier.

The rank is real rank and communication is deterministic. The general bound has improved from the $O(\sqrt r\log r)$ bound of the supplied source to $O(\sqrt r)$ in Sudakov--Tomon. [S1][E1] Hambardzumyan--Lovett--Shirley give a signed sum of $O(r\log(2r))$ rectangle indicators for a rank-$r$ $0/1$ matrix. Removing cancellations with quasipolynomial overhead remains conjectural, not part of their theorem. [E2] We therefore investigate how to organize a rectangle representation rather than simply find a low-rank factorization.

Attack route.

Put $B=(M_f+\mathbf1)/2$, so the two ranks differ by at most one and the communication costs agree up to an output convention. Write \begin{equation}\label{wsref-0-33-30-30-30-36-34-30-32-3a-73-69-67-6e-65-64} B(x,y)=\sum_{i=1}^t\epsilon_i1_{A_i}(x)1_{B_i}(y), \qquad\epsilon_i\in\{-1,1\}. \end{equation} One possible missing step is to organize one party's sets into few laminar families; another is to extract a large rectangle with very small error. The first produces an explicit protocol, but the universal one-sided version will fail even for a low-communication matrix. That failure identifies a need for adaptive two-sided structure, not a log-rank counterexample.

Attempt: a laminar protocol and its limitation.

A family is laminar if any two sets are nested or disjoint. Suppose the $A_i$ in (30006402:signed) split into $k$ laminar families. Identify duplicate sets. In each family Alice sends the index of the smallest set containing $x$, or a symbol for none. The sets containing $x$ form a chain; another set contains $x$ exactly when it contains that smallest set. Bob reconstructs all membership bits and evaluates the signed sum. Thus \begin{equation}\label{wsref-0-33-30-30-30-36-34-30-32-3a-70-72-6f-74-6f-63-6f-6c} D(f)\le k\lceil\log_2(t+1)\rceil+1, \end{equation} including an optional final answer bit. Signs and cancellations cause no problem once the full membership pattern is known. The same argument works with the parties exchanged.

Each family has at most $t+1$ membership patterns, hence $k$ such families produce at most $(t+1)^k$ distinct rows. This bound holds for any signed representation, not just a chosen decomposition. Define $I_s$ with rows all subsets $S\subseteq[s]$, columns $j\in[s]$, and entries $1_{j\in S}$, and form \[ B_s=\begin{pmatrix}I_s&0\\0&I_s^{\mathsf T}\end{pmatrix}. \] Singleton rows show $\operatorname{rank}I_s=s$, so $\operatorname{rank}B_s=2s$. There are at least $2^s$ distinct rows and at least $2^s$ distinct columns. Any one-sided laminarization of any signed rectangle representation, on either side, therefore satisfies \begin{equation}\label{wsref-0-33-30-30-30-36-34-30-32-3a-6f-62-73-74-72-75-63-74-69-6f-6e} k\log_2(t+1)\ge s. \end{equation} Thus quasipolynomial $t$ and polylogarithmic $k$ cannot both hold universally. The sign matrix $2B_s-\mathbf1$ has rank at most $2s+1$.

Nevertheless $B_s$ has a protocol using at most $\lceil\log_2s\rceil+3$ bits: each party announces its block; off-diagonal blocks output zero. On the first diagonal block Bob sends $j$, and on the second Alice sends $j$; the other party returns the membership bit. Thus the failed strengthening is global one-sided compression, not the desired communication upper bound. The example even has a positive rectangle partition; cancellations are not its obstruction.

A second route: eliminate a sufficiently small minority.

Here is a direct low-error extraction argument of the type in the source's Claim 4.1; no novelty is asserted. [S1] Let a sign matrix of rank at most $r\ge1$ have negative fraction $\eta\le1/(8r)$. At least half its rows have negative density at most $2\eta$. Choose a basis of their row space consisting of $q\le r$ such good rows, and retain columns where all basis rows are $+1$. A union bound retains at least $1-2q\eta\ge3/4$ of the columns. Every good row is a linear combination of the basis rows and hence constant on the retained columns. It cannot be $-1$ there: its negative fraction is at most $2\eta\le1/4$, whereas at least $3/4$ of the columns were retained. Thus there is an all-positive rectangle with at least $3/8$ of the original area.

Consequently this additional assertion would suffice: every rank-$r$ sign matrix contains a rectangle of relative area at least $2^{-(\log(r+2))^c}$ on which the minority sign has density at most $1/(8r)$, for one fixed $c$. Extraction gives a monochromatic rectangle of comparable area. The Nisan--Wigderson reduction, stated in the source's Theorem 1.4 and proved in Section 4.1, then gives a polylogarithmic deterministic protocol. [S1] The condition must apply uniformly at all ranks and all submatrices; one favorable rectangle in the original matrix does not justify recursive use. The signed decomposition theorem alone has not provided this bias estimate.

Stress test.

A positive term in a signed sum is not a nondeterministic acceptance certificate, since other terms can cancel it. Randomized approximation of the sum does not establish deterministic communication. Equation (30006402:obstruction) applies even after replacing the rectangles, so a new decomposition does not repair the one-sided proposal. But the explicit short protocol shows that proposal was stronger than log-rank in a structurally misleading way.

The script checks exact ranks, membership counts and the displayed protocol for $1\le s\le5$, the low-error extraction on all $3\times3$ sign matrices meeting its hypothesis, and additional planted examples. Those checks audit finite identities and the extraction proof, not the missing universal polylogarithmic estimate.

\Needspace{8\baselineskip}

Outcome.

Outcome: Exploratory approach with unresolved gap. A signed-rectangle protocol criterion was proved, and an explicit family refutes its natural universal one-sided strengthening while itself having low communication complexity. A separate low-error extraction lemma isolates a sufficient bias estimate, still unproved. Adaptive two-sided compression or a stronger bias argument remains necessary.

Sources

• S1 S. Lovett, 'Communication is bounded by root of rank', arXiv:1306.1877, 2013; also in Proc. 29th IEEE Conf. on Computational Complexity (CCC), 2014. https://arxiv.org/html/1306.1877v2. Catalogue formulation source.
• E1 B. Sudakov and I. Tomon, Matrix discrepancy and the log-rank conjecture, Mathematical Programming 212 $2025$, 567--579; Theorem 1.1 and communication consequence, online 5 July 2024. https://doi.org/10.1007/s10107-024-02117-9.
• E2 L. Hambardzumyan, S. Lovett and M. Shirley, The Log-Rank Conjecture: New Equivalent Formulations, CCC 2026, LIPIcs 383, 7:1--7:9; arXiv:2510.02583v2, Theorem 1.2 and Corollary 1.4. https://arxiv.org/html/2510.02583v2.