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.


1 Answer 1


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".

  • 2
    $\begingroup$ To be fair, I think it's only "clear" once you've seen the reduction :). $\endgroup$ Aug 23, 2017 at 20:52
  • $\begingroup$ Right :) it requires to read the page where lemma 3 appears. $\endgroup$
    – anps
    Aug 24, 2017 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$ Aug 24, 2017 at 12:48
  • $\begingroup$ @JoshuaGrochow It is not clear. $\endgroup$
    – Turbo
    Dec 21, 2017 at 19:05

Your Answer

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

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