The tag has no wiki summary.

learn more… | top users | synonyms

11
votes
1answer
348 views

Expressing Determinant as Permanent

One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is ...
5
votes
1answer
145 views

Size of Formulas with no negative sign for Matrix Permanent

What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would ...
3
votes
0answers
101 views

Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$. We know that the problem is ...
9
votes
2answers
403 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
180 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 ...
0
votes
2answers
225 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?
19
votes
2answers
810 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 ...
3
votes
0answers
153 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]$. ...
3
votes
1answer
212 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 ...
14
votes
2answers
307 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
370 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
366 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
490 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
420 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
226 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
311 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 ...
20
votes
5answers
1k 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?
21
votes
2answers
688 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 ...
6
votes
1answer
525 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$, ...
16
votes
1answer
665 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 ...
13
votes
1answer
370 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 ...