3
$\begingroup$

I am interested in highly parallel algorithms for computing the determinant of matrices of a special form (over finite fields).

It is known that computing determinant of general matrices over finite fields is in NC2. I've been wondering whether something better is known (hopefully NC1) for the (say, lower) Hessenberg matrix.

If it helps, it is further restricted so that its subdiagonal is all 1's, and all I care about is whether the determinant is 0 or not.

$\endgroup$
3
$\begingroup$

Sorry, this is clearly unlikely. Otherwise, it would be possible to use the algorithm to solve any NL\poly problem in NC1 via a reduction to evaluating the determinant of a Hessenberg matrix over a sufficiently large field. The reduction appears as Lemma 3 (and related discussion) in "Perfect constant-round secure computation via perfect randomizing polynomials".

$\endgroup$
  • 2
    $\begingroup$ To be fair, I think it's only "clear" once you've seen the reduction :). $\endgroup$ – Joshua Grochow Aug 23 '17 at 20:52
  • $\begingroup$ Right :) it requires to read the page where lemma 3 appears. $\endgroup$ – anps Aug 24 '17 at 7:35
  • $\begingroup$ and to know about the paper in the first place. I would not have thought to look in a paper with that title while thinking about your question. $\endgroup$ – Joshua Grochow Aug 24 '17 at 12:48
  • $\begingroup$ @JoshuaGrochow It is not clear. $\endgroup$ – T.... Dec 21 '17 at 19:05

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.