The permanent tag has no wiki summary.
7
votes
2answers
311 views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
8
votes
0answers
128 views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
2
votes
2answers
139 views
The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers
How much easier is computing the permanent of a matrix with only zeroes and ones than a matrix of only integers?
18
votes
2answers
521 views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
13
votes
1answer
351 views
Do the proofs that permanent is not in uniform $\mathsf{TC^0}$ relativize?
This is a follow up to this question, and is related to this question of Shiva Kinali.
It seems that the proofs in these papers (Allender, Caussinus-McKenzie-Therien-Vollmer, Koiran-Perifel) use ...
3
votes
1answer
198 views
examples of use of permanents
It is known that if calculating permanent is easy, then solving hard problems in NP is easy. Is there a transparent example regarding application of say finding independent set or find chromatic ...
3
votes
0answers
141 views
An ETH-hardness sparsity transition for the permanent
Let $A$ be an $n \times n$ matrix with $0$ or $1$ as entries. Under ETH, the permanent of $A$ cannot be calculated in $exp(o(n))$ time.
Consider $A$ has $O(n^{r})$ entries as $0$ where $r \in [0,2]$. ...
17
votes
5answers
836 views
About properties of adjacency matrix when a graph is planar
1- Is there any specific properties for adjacency matrix when a graph is planar?
2- Is there any thing special for computing the permanent of adjacency matrix when a graph is planar?
12
votes
2answers
278 views
A question to the #P-complete proof of the permanent from Ben-Dor/Halevi
In the paper of Ben-Dor/Halevi [1] it is given another proof that the permanent is
$\#P$-complete. In the later part of the paper, they show the reduction chain
\begin{equation}
\text{IntPerm} \propto ...
4
votes
1answer
342 views
Is beating the quadratic bound or improving the upper bound hard for permanents?
Let $A$ be a given square matrix. Is there any evidence that beating quadratic lower bounds for $B$ such that $\text{det}(B) = \text{per}(A)$ could be hard?
By this I mean are there any hints such ...
7
votes
1answer
256 views
Exact arithmetic complexity of Ryser's formula for computing permanent
What is the exact number of multiplication operations and addition operations needed to calculate the permanent in Ryser's formula (both original and the Gray coded version)?
I am looking reference ...
8
votes
1answer
436 views
Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants
Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known ...
5
votes
1answer
318 views
Permanent as projection of determinant and another permanent
I am looking for explicit examples where permanent of a given matrix $A$ is given by a determinant of a larger matrix $B$ (projection in the sense of Valiant). Is there any reference where I can find ...
-2
votes
1answer
202 views
Complexity of counting the number of Good-perfect matching in the bipartite graph
Let's $G=(U, V, E)$ be a balanced bipartite graph which $|U|=|V|=n$ and $|E|=n*(n-1)$; All nodes in $U$ are connected to all nodes in $V$ except $u_i$ to $v_i$ for $1\leq i \leq n$.
Definition1: ...
1
vote
1answer
300 views
The Relationship between P^NP and the Permanent
In the lecture notes Introduction to Complexity Theory by Goldreich, there is a section called "How close is $\#P$ is to $NP$". It is stated there that a $P^{NP}$ machine would approximate $\#P$ in ...
21
votes
2answers
611 views
Is there a direct/natural reduction to count non-bipartite perfect matchings using the permanent?
Counting the number of perfect matchings in a bipartite graph is immediately reducible to computing the permanent. Since finding a perfect matching in a non-bipartite graph is in NP, there exists ...
17
votes
1answer
619 views
Can we decide whether a permanent has a unique term?
Suppose we are given an n by n matrix, M, with integer entries. Can we decide in P whether there is a permutation $\sigma$ such that for all permutations $\pi\ne\sigma$ we have $\Pi M_{i\sigma(i)}\ne ...
0
votes
0answers
219 views
computing the permanent [closed]
I know that computing the permenant even for a 0-1 matrix is #p-comp, what about a matrix which whole its aij=1? I think computing the permenent for a n*n matrix filled whole with 1 is not still ...
7
votes
1answer
481 views
Permanents - Approximation and connection to integer factorization
Given a non-negative integer matrix of size $n \times n$. If the permanent can be calculated in $n^{2}$ arithmetic operations but each operation is on word size $n^{k}$ bits for some constant $k$, ...
