All Questions

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?). Let $\omega(n)$ be number of distinct ...

The permanent of an $n$-by- $n$ matrix $A=\left(a_{i j}\right)$ is defined as $$ \operatorname{perm}(A)=\sum_{\sigma \in S_{n}} \prod_{i=1}^{n} a_{i, \sigma(i)} $$ The sum here extends over all ...

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree. MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...

My question concerns approximating permanent of an $n$-by-$n$ matrix. Several approximation algorithms have been proposed in the literature for this purpose, whose time complexity depend on $n$ and ...

This Lecture summarizes some well known facts about $\#P$ completeness of permanent. Given a CNF formula $\phi$ on $n$ variables, they construct matrix $A$ such that: $$perm(A)=4^{3m} \#SAT(\phi)$$ ...