Rank bounds for grid tensor decompositions
A grid tensor can enforce matching labels along edges by assigning 1 when both ends of every edge carry the same label and 0 otherwise. A cut rearranges the tensor into a matrix, with the labels on one side indexing rows and the rest indexing columns. How small can the sum of the smaller row-cut and column-cut ranks be when the tensor is written as a sum of arbitrary terms?
Why it matters and what counts as progress
Why it matters: The two matrix ranks constrain how efficiently a decomposition can represent the same grid constraints using row or column groupings. Correlations between terms matter in grid-based algorithms that count satisfying assignments.
What counts as progress: Prove a stronger lower bound for a specified grid and pair of cuts, or construct a decomposition that reaches the bound. For a network-cost result, specify how the network is grouped and charged.
How the problem developed
Anthropic and OpenAI The reported subexponential counting algorithms prompted study of limits on the ways local constraints can be grouped.
- 30 Oct 2026 · Bounds for product terms [2]
Ruhollah Majdoddin Bounded a class of grid recursions built from product terms and asked what happens when the terms can be correlated.
Vaibhav Tulsyan with Claude Gave the smaller-cut rank-sum bound for a grid tensor. Tulsyan reports that Lean checked the inequality.
AI contribution
What the ETH refutations do not give: barriers for the counting engines, with machine-checked lemmas
For the graph tensor on a grid with 18 edges joining cells in different rows and columns, take any finite sum of tensors equal to the graph tensor over a field. For each summand, take the smaller of the two matrix ranks obtained by cutting off the last row or the last column. If the edge labels range over a nonempty alphabet of size , the sum of these smaller ranks is at least .
Sources
Publication history
Daily emails by default, only when there’s an update.