0
$\begingroup$

By $'$ I mean transpose. I gather the info here from rjlipton.wordpress.com/2014/12/21/modulating-the-permanent. We know that if $U\in\Bbb F_{3^t}^{n\times n}$ satisfies $UU'=I_n$ in $\Bbb F_{3^t}$ then we can compute $Perm(U)$ in $\Bbb F_{3^t}$ in $O(n^4)$ time.

This gives an $O(n^4)$ time algorithm for $Perm(U)\bmod 3$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n$ in $\Bbb Z$?

Can it be modified to give an $O(n^{O(t)})$ time algorithm for $Perm(U)\bmod 3^t$ for $U\in\Bbb Z^{n\times n}$ satisfying $UU'=I_n\bmod 3^r$ in $\Bbb Z$ where $r\in\Bbb N$ is fixed?

Improve this question
$\endgroup$
11
  • $\begingroup$ @EmilJeřábek first sentence follows from here rjlipton.wordpress.com/2014/12/21/modulating-the-permanent right? $\endgroup$
    – Turbo
    Aug 4, 2017 at 11:35
  • $\begingroup$ @EmilJeřábek done including. $\endgroup$
    – Turbo
    Aug 4, 2017 at 11:40
  • 1
    $\begingroup$ The only matrices $U \in \mathbb{Z}^{n \times n}$ satisfying $UU^T=I$ are signed permutation matrices, for which it is trivial to compute the permanent... $\endgroup$
    – Joshua Grochow
    Aug 9, 2017 at 5:23
  • $\begingroup$ Interesting I did not know that but 2. still remains $\endgroup$
    – Turbo
    Aug 9, 2017 at 5:32
  • 1
    $\begingroup$ @777 oops, my bad. didn't realise you were asking about char 3. Now it makes sense! $\endgroup$
    – Nikhil
    Aug 9, 2017 at 17:05

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.