Group constructions and the Set Cover tensor threshold
Follow the latest progress by email.
Can a finite group encode balanced tripartitions efficiently enough to beat the tensor-rank threshold in the Set Cover reduction? The allowed method maps triples of k-subsets of a 3k-element set into a group, with a product equal to the identity on disjoint triples. Weighted degenerations and joint constructions on tensor powers give broader versions of the question.
Why it matters and what counts as progress
Why it matters: This route connects exact exponential algorithms with algebraic tensor methods. A barrier identifies which construction families cannot yield the desired algorithmic improvement.
What counts as progress: Prove a sharp group-size bound under the stated restriction or degeneration rules, extend it to tensor powers, or find a construction outside those rules that crosses the threshold. Distinguish a barrier for one method from a general tensor-rank lower bound.
How the problem developed
- 5 Nov 2023 · Research result [1]
Kevin Pratt Related the Set Cover Conjecture to the asymptotic rank of balanced tripartitioning tensors and gave a finite-group construction. The work appeared at STOC 2024.
Eyal Merhavi with Anthropic Claude Reported general-group rigidity and group-size barriers for restrictions and weighted degenerations, including tensor powers. The exact-source mechanical check completed; the unrestricted tensor-rank problem is outside the result.
Selected milestones connect the cited tensor method with the scoped group-construction barrier. Earlier literature and unrestricted constructions remain separate.
AI contribution
Group constructions cannot refute the Set Cover Conjecture, including tensor powers
For k≥2 and m≥1, a Strassen combinatorial degeneration of a finite group tensor onto the mth tensor power of the balanced tripartitioning tensor T_k requires |G|≥binom(3k,⌊3k/2⌋)^m>τ_k^m, where τ_k=8^k binom(3k,k)binom(2k,k)/27^k. For single-copy group restrictions, |G|≥2^{3k−1}; the partition products factor through commuting elements even when G is nonabelian.
Sources
Website timeline
Publication dates and editorial changes.
Group constructions cannot refute the Set Cover Conjecture, including tensor powers