3

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?

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

2 Answers2

3

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}!)$.

Yuval Filmus
  • 57,157
1

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.

D.W.
  • 4,540