3
$\begingroup$

Let $f\in \Bbb Z[x_1,\dots,x_n]$ be a multivariate polynomial.

Is it possible to represent $f$ say of TOTAL degree $d$ by a $({dc})^{n}\times ({dc})^{n}$ determinant or $({dn})^c\times ({dn})^c$ permanent with polynomial entries with some fixed $c\geq 1$ so that each entry of the matrix is a linear functional of $x_i$ (note determinant size is exponential in $n$ and permanent size is polynomial in $n$ because there conjecture is a strong conjecture which states permanent polynomial cannot be represented as a determinant polynomial coming from a polynomial sized matrix)?

Are there standard procedures?

What if $f$ is multilinear?

$\endgroup$

migrated from cs.stackexchange.com Dec 15 '14 at 21:56

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ I'm not sure why this question was migrated. It belongs to algebraic complexity theory, which is a part of theoretical computer science. $\endgroup$ – Yuval Filmus Dec 15 '14 at 22:38
1
$\begingroup$

Yes, this is possible. Let $M$ be the $1\times 1$ matrix whose only entry is $f$. Then $\det M = f$, so we have the desired representation. If you wanted a larger matrix, just add ones down the diagonal and zeroes everywhere else, and you've got it.

$\endgroup$
  • $\begingroup$ I see the question cannot be framed nicely. $\endgroup$ – T.... Dec 14 '14 at 1:47
3
$\begingroup$

The usual notion of projection has each entry being a linear expression in the inputs, or (equivalently) either an input or a constant. Algebraic circuit size should be polynomially related to "determinant size", even when $f$ is not multilinear. Since each polynomial of degree $d$ has at most $\sum_{c \leq d} \binom{n+c}{c}$ monomials, it has circuit size $O(n^d)$, and so can be expressed as a projection of the determinant of an $O(n^{O(d)}) \times O(n^{O(d)})$ matrix. For the permanent we have $d = \sqrt{n}$ so this bound is pretty big. I believe the actual circuit size for permanent is actually at most exponential in $n$, which is slightly better than the trivial bound $O(\sqrt{n}\cdot \sqrt{n}!)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.