Strong USP capacity conjecture

A strong USP is a collection of strings with the strong uniquely solvable puzzle property, and the strong USP capacity is the largest constant CC such that there exist strong USPs of size (Co(1))k(C-o(1))^k and width kk for infinitely many values of kk. The USP capacity equals 3/22/33/2^{2/3}.

Strong USP capacity conjecture. The strong USP capacity equals

3/22/3.3/2^{2/3}.

This would show that strong USPs attain the same asymptotic capacity as USPs and, via the associated group-theoretic construction, would yield matrix multiplication exponent ω=2\omega=2. The paper gives a lower bound of 22/32^{2/3} for the strong USP capacity but no matching upper bound beyond the general USP-capacity bound.

Sources & referencesView supporting material

Primary source

Henry Cohn, Robert Kleinberg, Balazs Szegedy and Christopher Umans, “Group-theoretic algorithms for matrix multiplication”, arXiv:math/0511460 (2005).

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.