Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR11-169 | 2nd March 2012 02:54

Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation

RSS-Feed




Revision #2
Authors: Leonid Gurvits
Accepted on: 2nd March 2012 02:54
Downloads: 1423
Keywords: 


Abstract:

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\begin{equation} \label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n
\end{equation}
We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\
For all pairs of $n \times n$ matrices $(P,Q)$, where $P$ is nonnegative and $Q$ is doubly-stochastic
\begin{equation} \label{st}
\log(per(P)) \geq \sum_{1 \leq i,j \leq n} \log(1- Q(i,j)) (1- Q(i,j)) - \sum_{1 \leq i,j \leq n} Q(i,j) \log \left(\frac{Q(i,j)}{P(i,j)} \right
)
\end{equation}
The main co
rollary of (\ref{st}) is the following inequality for doubly-stochastic matrices:
$$
\frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} \left(1- A(i,j)\right)^{1- A(i,j)}.
$$
{\bf We use this inequality to prove Friedland's conjecture on monomer-dimer entropy, so called {\it Asymptotic Lower Matching Conjecture}}\\
We present explicit doubly-stochastic $n \times n$ matrices $A$ with
the ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$ and conjecture that
$$
\max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx \left(\sqrt{2} \right)^{n}.
$$
If true, it would imply a deterministic poly-time algorithm to approximate the permanent of $n \times n$ nonnegative
matrices within the relative factor $\left(\sqrt{2} \right)^{n}$.\\



Changes to previous version:

A lot of editing, a new section on correlational inequalities
is added.


Revision #1 to TR11-169 | 1st March 2012 05:26

Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation





Revision #1
Authors: Leonid Gurvits
Accepted on: 1st March 2012 05:26
Downloads: 1460
Keywords: 


Abstract:

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\begin{equation} \label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n
\end{equation}
We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\
For all pairs of $n \times n$ matrices $(P,Q)$, where $P$ is nonnegative and $Q$ is doubly-stochastic
\begin{equation} \label{st}
\log(per(P)) \geq \sum_{1 \leq i,j \leq n} \log(1- Q(i,j)) (1- Q(i,j)) - \sum_{1 \leq i,j \leq n} Q(i,j) \log \left(\frac{Q(i,j)}{P(i,j)} \right
)
\end{equation}
The main co
rollary of (\ref{st}) is the following inequality for doubly-stochastic matrices:
$$
\frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} \left(1- A(i,j)\right)^{1- A(i,j)}.
$$
{\bf We use this inequality to prove Friedland's conjecture on monomer-dimer entropy, so called {\it Asymptotic Lower Matching Conjecture}(LAMC)\\
We use some ideas of our proof of (LAMC) to disprove [Lu,Mohr,Szekely]
positive correlation conjecture.
We present explicit doubly-stochastic $n \times n$ matrices $A$ with
the ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$ and conjecture that
$$
\max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx \left(\sqrt{2} \right)^{n}.
$$
If true, it would imply a deterministic poly-time algorithm to approximate the permanent of $n \times n$ nonnegative
matrices within the relative factor $\left(\sqrt{2} \right)^{n}$.\\



Changes to previous version:

A section on monomer-dimer problem is seriously revised;
a new section with a disproof of
[Lu,Mohr,Szekely] is added. The current version is
longer and cleaner.


Paper:

TR11-169 | 14th December 2011 23:59

Unleashing the power of Schrijver's permanental inequality with the help of the Bethe Approximation





TR11-169
Authors: Leonid Gurvits
Publication: 15th December 2011 08:06
Downloads: 1600
Keywords: 


Abstract:

Let $A \in \Omega_n$ be doubly-stochastic $n \times n$ matrix. Alexander Schrijver proved in 1998 the following remarkable inequality
\begin{equation} \label{le}
per(\widetilde{A}) \geq \prod_{1 \leq i,j \leq n} (1- A(i,j)); \widetilde{A}(i,j) =: A(i,j)(1-A(i,j)), 1 \leq i,j \leq n
\end{equation}
We prove in this paper the following generalization (or just clever reformulation) of (\ref{le}):\\
For all pairs of $n \times n$ matrices $(P,Q)$, where $P$ is nonnegative and $Q$ is doubly-stochastic
\begin{equation} \label{st}
\log(per(P)) \geq \sum_{1 \leq i,j \leq n} \log(1- Q(i,j)) (1- Q(i,j)) - \sum_{1 \leq i,j \leq n} Q(i,j) \log \left(\frac{Q(i,j)}{P(i,j)} \right
)
\end{equation}
The main co
rollary of (\ref{st}) is the following inequality for doubly-stochastic matrices:
$$
\frac{per(A)}{F(A)} \geq 1; F(A) =: \prod_{1 \leq i,j \leq n} \left(1- A(i,j)\right)^{1- A(i,j)}.
$$
{\bf We use this inequality to prove Friedland's conjecture on monomer-dimer entropy, so called {\it Asymptotic Lower Matching Conjecture}}\\
We present explicit doubly-stochastic $n \times n$ matrices $A$ with
the ratio $\frac{per(A)}{F(A)} = \sqrt{2}^{n}$ and conjecture that
$$
\max_{A \in \Omega_n}\frac{per(A)}{F(A)} \approx \left(\sqrt{2} \right)^{n}.
$$
If true, it would imply a deterministic poly-time algorithm to approximate the permanent of $n \times n$ nonnegative
matrices within the relative factor $\left(\sqrt{2} \right)^{n}$.\\



ISSN 1433-8092 | Imprint