[I was reading something I thought was totally unrelated and then had an "aha moment" so I think I've figured out at least part of the answer. I'm not sure if this is what Gurvits had in mind, but this makes sense to me.]
A distribution on n binary variables $x_1,...,x_n$ can be viewed as an element of the tensor product $\mathbb{R}^2 \otimes \dotsb \otimes \mathbb{R}^{2}$ (n factors) (actually the associated projective space, but we'll get to that). If we label the basis elements of each copy of $\mathbb{R}^2$ by $|0\rangle$ and $|1\rangle$, then a basis of this tensor product space is given by the set of all n-bit strings. If we have an element of this tensor product whose coefficients sum to 1, then we can interpret the coefficient of any given n-bit string as the probability of that string occurring -- whence, a probability distribution! Now, since we only want probability distributions (coefficients summing to 1) we can normalize any vector in the tensor product to have that property. By only considering normalized tensors, we are really only considering elements of the projective space of this tensor product.
Now we have to connect tensor-rank to Deolalikar's notion of polylog-parametrizability. According to this page by Terry Tao, it seems that Deolalikar's notion of polylog-parametrizability is that the distribution $\mu$ can be "factored into potentials" as $\mu(x_1,...,x_n) = \prod_{i=1}^{n} p_i(x_i ; x_{pa(i)})$ where pa(i) is a set of polylog(n) variables, defined to be the "parents of i" and $p_i( - ; x_{pa(i)})$ is a distribution on $x_i$ that depends only on these parent variables. Moreover, the directed graph of parents should be acyclic.
Let's start with a very simple kind of distribution. Suppose $\mu$ satisfies $\mu(x_1, ..., x_n) = \prod_{i=1}^{n} p_i(x_i)$ for some distributions $p_i$ (where $p_i$ depends only on $x_i$). Then it is hopefully clear that the corresponding tensor is the rank 1 tensor: $(p_1(0)|0\rangle + p_1(1)|1\rangle) \otimes \dotsb \otimes (p_n(0)|0\rangle + p_n(1)|1\rangle)$.
For a slightly more complicated distribution, suppose we want to consider the uniform distribution over the strings where $x_{2i} = 1 - x_{2i+1}$ (they are each other's negation) for all $i$. In Tao's interpretation of Deolalikar's language, this would be a $O(1)$-parametrizable distribution. Then this corresponds to the tensor $(|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle) \otimes \dotsb \otimes (|0\rangle \otimes |1\rangle + |1\rangle \otimes |0\rangle)$ (needs to be normalized). If we write this out in full, it contains $2^{n/2}$ terms, and so has tensor-rank at most $2^{n/2}$ over $\mathbb{R}^2$. However, over $\mathbb{R}^2 \otimes \mathbb{R}^2$, it has tensor-rank 1! I believe the latter fact corresponds to the fact that the factorization can be described by $O(n)$ numbers -- $O(1)$ for each pair of adjacent bits, for each of $O(n)$ adjacent pairs. Significantly smaller than the $2^n$ real numbers required in theory for an arbitrary distribution mu on the Boolean cube.
I'm still having trouble formulating two issues, and would appreciate further answers on them:
- Making the latter correspondence precise
- Writing out the formulae for the tensor corresponding to polylog-parametrizable distribution, and getting an upper bound on its rank.
