Capacity of Uniquely Solvable Puzzle (USP)

Question

In their seminal paper Group-theoretic algorithms for matrix multiplications, Cohn, Kleinberg, Szegedy and Umans introduce the concept of uniquely solvable puzzle (defined below) and USP capacity. They claim that Coppersmith and Winograd, in their own groundbreaking paper Matrix multiplication via arithmetic progressions, "implicitly" prove that the USP capacity is $3/2^{2/3}$. This claim is reiterated in several other places (including here on cstheory), yet nowhere is an explanation to be found. Below is my own understanding on what Coppersmith and Winograd do prove, and why it's not enough.

Is it true that the USP capacity is $3/2^{2/3}$? If so, is there a reference for the proof?

Uniquely solvable puzzles

A uniquely solvable puzzle (USP) of length $n$ and width $k$ consists of a subset of $\{1,2,3\}^k$ of size $n$, which we also think of as three collections of $n$ "pieces" (corresponding to the places where the vectors are $1$, the places where they are $2$, and the places where they are $3$), satisfying the following property. Suppose we arrange all the $1$-pieces in $n$ lines. Then there must be a unique way to put the other pieces, one of each type in each line, so that they "fit".

Let $N(k)$ be the maximum length of a USP of width $k$. The USP capacity is $$ \kappa = \sup_k N(k)^{1/k}. $$ In a USP, each of the pieces needs to be unique - that means that no two lines contain a symbol $c \in \{1,2,3\}$ in exactly the same places. This shows (after a short argument) that $$ N(k) \leq \sum_{a+b+c=k} \min \left\{ \binom{k}{a}, \binom{k}{b}, \binom{k}{c} \right\} \leq \binom{k+2}{2} \binom{k}{k/3}, $$ and so $\kappa \leq 3/2^{2/3}$.

Example (a USP of length $4$ and width $4$): $$\begin{align*} 1111 \\ 2131 \\ 1213 \\ 2233 \end{align*}$$ Non-example of length $3$ and width $3$, where the $2$- and $3$-pieces can be arranged in two different ways: $$\begin{align*} 123 && 132 \\ 231 && 321 \\ 312 && 213 \end{align*}$$

Coppersmith-Winograd puzzles

A Coppersmith-Winograd puzzle (CWP) of length $n$ and width $k$ consists of a subset $S$ of $\{1,2,3\}^k$ of size $n$ in which the "pieces" are unique - for any two $a \neq b \in S$ and $c \in \{1,2,3\}$, $$ \{ i \in [k] : a_i = c \} \neq \{ i \in [k] : b_i = c \}. $$ (They present it somewhat differently.)

Every USP is a CWP (as we commented above), hence the CWP capacity $\lambda$ satisfies $\lambda \geq \kappa$. Above we commented that $\lambda \leq 3/2^{2/3}$. Coppersmith and Winograd showed, using a sophisticated argument, that $\lambda = 3/2^{2/3}$. Their argument was simplified by Strassen (see Algebraic complexity theory). We sketch a simple proof below.

Given $k$, let $V$ consist of all vectors containing $k/3$ each of $1$s, $2$s, $3$s. For $c \in \{1,2,3\}$, let $E_c$ consist of all pairs $a,b \in V$ such that $\{ i \in [k] : a_i = c \} = \{ i \in [k] : b_i = c \}$, and put $E = E_1 \cup E_2 \cup E_3$. Every independent set in the graph $G = (V,E)$ is a CWP. It is well-known that every graph has an independent set of size $|V|^2/4|E|$ (proof: select each vertex with probability $|V|/2|E|$, and remove one vertex from each surviving edge). In our case, $$ |V| = \binom{k}{k/3} \binom{2k/3}{k/3}, \quad |E| \leq 3|E_1| = \frac{3}{2}\binom{k}{k/3} \binom{2k/3}{k/3}^2. $$ Hence $$ \frac{|V|^2}{4|E|} = \frac{1}{6} \binom{k}{k/3} \Longrightarrow \lambda \geq \frac{3}{2^{2/3}}. $$

Answer 1

Like many other questions, the answer to this one can be found in Stothers' thesis. A local USP is a CWP in which the only way in which a 1-piece, a 2-piece and a 3-piece can fit together is if their union is in $S$. Clearly a local USP is a USP, and a construction from [CKSU] shows that the USP capacity is achieved by local USPs (we are going to show that constructively).

Coppersmith and Winograd construct an almost 2-wise independent distribution $S$ on $2^V$ with the following two properties: (1) $\Pr[x \in S] = (|V|/2|E|)^{1-\epsilon}$, (2) For any $x,y,z \in V$ such that the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ together form a vector $w \in V$: if $x,y,z \in S$ then $w \in S$.

We choose a random subset $S$ of $V$ according to the distribution, and for each edge $(x,y) \in E$, we remove both vertices $x,y$. The expected number of vertices left is roughly $(|V|^2/2|E|)^{1-\epsilon}$. The resulting set $T$ is a local USP: if there are $x,y,z \in T$ in which the 1-piece of $x$, the 2-piece of $y$ and the 3-piece of $z$ fit, forming a piece $w$, then $x,y,z,w \in S$, and so all of $x,y,z$ are removed from $S$.