Lovett–Singer–Sudan conjecture on cross-intersecting set systems

Let S={S1,,Sm}\mathcal{S}=\{S_1,\ldots,S_m\} and T={T1,,Tn}\mathcal{T}=\{T_1,\ldots,T_n\} be families in 2[d]2^{[d]}, and suppose that (S,T)(\mathcal{S},\mathcal{T}) is {a,b}\{a,b\}-cross-intersecting, meaning that ST{a,b}|S\cap T|\in\{a,b\} for every SSS\in\mathcal{S} and TTT\in\mathcal{T}, where a,b{0,,d}a,b\in\{0,\ldots,d\}. Lovett–Singer–Sudan conjecture. There exist subfamilies AS\mathcal{A}\subseteq\mathcal{S} and BT\mathcal{B}\subseteq\mathcal{T} such that (A,B)(\mathcal{A},\mathcal{B}) is either {a}\{a\}- or {b}\{b\}-cross-intersecting, and

A,B2polylog(d)ST.|\mathcal{A}|,|\mathcal{B}|\geq 2^{-\operatorname{polylog}(d)}\cdot|\mathcal{S}||\mathcal{T}|.

This conjecture was independently proposed by Lovett and by Singer–Sudan, and the source says it is implied by the log-rank conjecture. The paper proves an equivalence between the two conjectures, so its resolution remains open.

Sources & referencesView supporting material

Primary source

Lianna Hambardzumyan, Shachar Lovett and Morgan Shirley, “The Log-Rank Conjecture: New Equivalent Formulations”, arXiv:2510.02583 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.