20
$\begingroup$

[Note: I believe this question in no way hinges on the correctness or incorrectness of Deolalikar's paper.]

On Scott Aaronson's blog Shtetl Optimized, in the discussion about Deolalikar's recent attempt on P vs NP, Leonid Gurvits made the following comment:

I tried to understand/reformulate the approach, and here is my, perhaps very minimalist, attempt: the discrete probabilistic distributions in the paper can be viewed as tensors, or very special multilinear polynomials. The assumptions “P=NP” somehow gives a (polynomial?) upper bound on the tensor rank. And finally, using known probabilistic results, he gets nonmatching (exponential?) lower bound on the same rank. If I am right, then this approah is a very clever, in a good sense elementary, way to push the previous algebraic-geometric approaches.

Despite the suspected/known flaws in Deolalikar's proof, I'm curious:

In what way can the distributions discussed in Deolalikar's paper be considered as tensors, and how do the statements of his results (regardless of their correctness) translate into statements about tensor-rank?

$\endgroup$
  • $\begingroup$ Just saw this. Why not ask Gurvits himself?... $\endgroup$ – Ryan Williams Sep 12 '10 at 0:45
  • 1
    $\begingroup$ @Ryan: I did :). He responded quickly that he's busy right now but will definitely get to it eventually. It's been a while and I was hoping someone here might be able to elucidate the remark faster. $\endgroup$ – Joshua Grochow Sep 12 '10 at 4:56
10
$\begingroup$

[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.
$\endgroup$
  • $\begingroup$ did you ever get back to this? $\endgroup$ – T.... Dec 4 '13 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.