Can the permanent of stable negative matrices be approximated?

Eric Vigoda is one of the top experts in the world in the area of Markov Chain Monte Carlo methods. He shared the prestigious Fulkerson Prize with Mark Jerrum and Alistair Sinclair for their brilliant work (JSV) on approximations to the permanent.

Today I would like to talk about JSV, and raise an open problem that I have thought about. The problem is an attempt to slightly generalize this famous theorem.

I have worked years ago on much more naive approaches to computing the permanent, than JSV’s approach. For example, with Narendra Karmarkar, Richard Karp, László Lovász, and Michael Luby we showed that a simple random algorithm could approximate the permanent, but unfortunately the variance of the method was in general exponential.

Eric is part of the theory group at Georgia Tech, and can always be counted on to add a wry comment to any discussion the group has. Yet I do not have any really cool stories about Eric. I could make one up, but so far all my stories are true. Well, what I mean exactly is that “I believe that all my stories are true.” This is an important difference: as I get older my memory for events could be wrong, but I can say that I think that all the stories that I have written are true.

Raymond Smullyan is a logician who has written many popular books on the theory of lying such as “What Is the Name of This Book?” His definition of lying is:

A person is lying if they say a statement that they believe is false.

Smullyan says there was once this poor fellow who was locked up for decades in a psychiatric hospital because he was sure that he was Napoleon. Every few years there was a sanity hearing to determine if he could be released. Each time he failed the part of the hearing where they asked him various questions, while checking his veracity with a lie detector.

Finally at one hearing, they were giving him his lie detector test and asking him various questions, when they asked him, “do you think that you are Napoleon?” He answered “no.” But, the needle on the detector jumped: he was lying. This is Smullyan’s definition of lying: saying something you know is false. The poor fellow knew he really was Napoleon.

In Smullyan’s sense I am clear. Let’s turn to approximations of the permanent.

Approximation of the Permanent

The permanent of a square matrix ${A}$ of order ${n}$ is, of course, equal to

$\displaystyle \mathsf{perm}(A) = \sum_{\pi} a_{1\pi_{1}} \cdots a_{n\pi_{n}}$

where the summation is over all permutations ${\pi}$ of ${\{1,2, \ldots, n\}}$.

Even though this looks similar to the determinant, the complexities of computing both could not be more different. While there is a polynomial time algorithm to compute the determinant, the computation of the permanent is ${\#}$P-complete. See here and here for more details. JSV’s great theorem is:

Theorem: For any ${c}$, there is a random polynomial time algorithm that computes the ${\mathsf{perm}(A)}$ to with a multiplicative factor of ${1+O(\frac{1}{n^{c}})}$, provided ${A}$ is non-negative matrix.

I will not explain the proof or even sketch it—see their paper for the details. I will, however, point out that there is an amplifier lurking here too. If instead the theorem proved a multiplicative factor of ${2}$, then that could easily be amplified to a multiplicative factor of ${1+O(\frac{1}{n^{c}})}$ for any ${c}$.

The key is a simple repetition amplifier. Suppose that ${A}$ is given, then create the matrix ${B}$,

$\displaystyle \left( \begin{array}{cc} A & 0 \\ 0 & A \end{array} \right).$

Then, note that ${\mathsf{perm}(B) = \mathsf{perm}(A)^{2}}$, which implies that knowing ${\mathsf{perm}(B)}$ to within a factor of ${2}$ implies an approximation to ${\mathsf{perm}(A)}$ of at most ${\sqrt 2}$. This can be done for more copies of ${A}$, which yields the claim. I find it interesting how powerful even such trivial amplifiers are. Do you agree?

Negative Entries are Hard

JSV points out that even allowing one negative entry would make their approximation problem NP-hard. This is because the negative entry allows cancellation, which allows the encoding of SAT. The method they use, is clever, but simple. I have a rule:

“Beware of simple counterexamples.”

What I mean is that often a simple counterexample may be hiding a theorem—the theorem will require some additional restriction, but may still be quite interesting.

Here is a classic example of my rule: the polynomial equation ${x^{2} = 0}$ shows that an equation can have less roots than its degree. This shows that the simple claim that a polynomial of degree ${d}$ has ${d}$ roots is wrong. But, there is a fix: if we count the roots properly, then we can restore the claim that a polynomial has ${d}$ roots.

I think that this type of behavior occurs throughout theory and mathematics. So if you see an almost trivial counterexample to something, stop and see if you can modify the theorem you are trying to prove. You may be pleasantly surprised.

I have decided to add this update:

Even allowing one negative entry would make the approximation problem equivalent to computing the permanent exactly.

The argument is simple: Let $A$ be a matrix and let $A(x)$ be the matrix with the $(1,1)$ entry set to $A_{11}-x$. Then, $\mathsf{perm}(A(x)) = \mathsf{perm}(A)-x \cdot \mathsf{perm}(B)$ where $B$ is the sub-matrix that results after removing the first row and column from $A$. An approximation method gives at least the sign of $\mathsf{perm}(A(x))$. Then, by binary search you can get the root of the equation $\mathsf{perm}(A)-x \cdot \mathsf{perm}(B)=0$. The permanent of $A$ itself follows from a recursion on this idea.

Can Negative Entries be Easy?

I think that we may be able to add negative entries to a matrix ${A}$ and still be able to compute an approximation to its permanent. This is in direct conflict with the fact that even one negative entry makes the problem NP-hard. Right. My idea is to add an extra condition to the matrix ${A}$ that will possibly allow the theorem to be true. Thus, our goal is to be able to prove:

“Theorem”: For any ${c}$, there is a random polynomial time algorithm that computes the ${\mathsf{perm}(A)}$ to with a multiplicative factor of ${1+O(\frac{1}{n^{c}})}$, provided ${A}$ is a matrix with property ${X}$.

The key is what is the property ${X}$? I have a suggestion—why else would I raise this anyway? Consider a matrix ${A}$ with exactly one entry that is negative and further assume that entry is ${-1}$. Call such a matrix a ${1}$negative matrix. A ${k}$-negative matrix would have ${k}$ negative entries; a ${0}$-negative matrix is a non-negative matrix.

Suppose that ${A}$ is a ${1}$-negative matrix, and let ${A_{ij} = -1}$. Define the matrix ${A^{(t)}}$ to be ${A}$ with the ${-1}$ replaced by ${t}$. Of course, ${A^{(-1)} = A}$.

The key property ${X}$, I think, is this: Say that ${A}$ is stable provided

$\displaystyle \left | \mathsf{perm}(A) - \mathsf{perm}(A^{(-1+\delta)}) \right | \le O(\mathsf{perm}(A))$

for ${\delta}$ small enough. The point is the permanent of the matrix ${A}$ does not change much as the value of ${-1}$ is perturbed slightly.

I believe that there is a good approximation algorithm that will work for such stable matrices. This hunch is based on: intuition, the observation that JSV’s counterexample is not stable, and finally on a nice connection to extrapolation.

Polynomial Extrapolation

The main idea is really simple. Again let ${A}$ be a ${1}$-non-negative stable matrix. Define, ${f(t)}$ to be ${\mathsf{perm}(A^{(t)})}$. Note, ${f(t)}$ is a linear polynomial: the ${t}$ entry can only be used at most once in any term of the permanent.

We want the value of ${f(-1)}$. However, using the JSV’s theorem we can get ${f(t)}$ for any natural number ${t}$ to within a small error. Thus, we are faced with an extrapolation problem:

Can we compute ${f(-1)}$ with small error from good approximations to ${f(0)}$ and ${f(1)}$ and so on?

Since ${A}$ is stable there seems to be some hope that this problem can be solved. It is an extrapolation problem because the point we want ${-1}$ is not in the interval of the points that we can evaluate.

Open Problems

The clear open problem is prove that a stable matrix with one negative entry has an approximation algorithm. Then, try to extend this to multiple negative entries. I really believe that this should be possible at least for a constant number of negative entries.

Another “meta” problem is: do matrices that arise in practice have the stability property? Or when do matrices have this property?

August 30, 2009 2:34 pm

Here is an interesting paper that is related to the ideas here on stable. It’s by Yonatan Bilu and Nathan Linial, and is at http://www.cs.huji.ac.il/~nati/PAPERS/stable_instance.pdf

August 30, 2009 2:53 pm

Why is it hopeless to have a poly-time approximation algorithm for matrices with negative elements? The fact that it is an NP-hard problem is not, by itself, a barrier…

August 30, 2009 4:35 pm

I am confused. I was just saying that finding a polynomial time approximate to matrices with negative coefficients would show that P=NP. I added an update to the post that says the following:

Actually, they show even more. If you could approximate even one negative entry then you could exactly evaluate the permanent. The argument is simple: Let A be a matrix and let A(x) be the matrix with the (1,1) entry set to A(1,1)-x. Then, perm(A(x)) = perm(A)-xperm(B) where B is the sub-matrix that results after removing the first row and column from A. An approximation method given the sign at least of perm(A(x)). Then, by binary search you can get the root of the equation perm(A)-xperm(B)=0. The permanent of A itself follows from a recursion on this idea.

Note, these matrices will not be stable in the sense that I use later on.

• December 22, 2014 8:07 am

Read the seminal paper by Valiant. Exact calculation of the permanent would mean the exact calculation of the satisfying assignments of a 3CNF. Which actually would mean more than P = NP, it would imply that #P is in FP.

What is funny is the Karp-reduction from integer matrices to non-negative matrices and then 0-1 matrices. The reduction uses modulo prime number calculations, and it seems to be crucial: the relative error is not preserved during mod p calculations, and this is an explanation why there is an FPRAS for calculating the permanent of non-negative matrices while it is still #P-complete.

August 30, 2009 3:22 pm

Does JSV’s theorem only work on 0-1 matrices? If not, isn’t B=kA (k>1) a much better amplifier, i.e. knowing an approximation to perm(B) within a factor of c will yield an approximation to perm(A) within a factor of c/(k^n).

August 30, 2009 4:37 pm

Yes they can handle integers but the matrix size blows up with the size of the coefficients. I should have stated a more careful theorem. Thus, uses a coefficient of size n in matrix will cost n in the size of the matrix, roughly.