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

CC BY-SA 3.0
2017-08-23T20:52:05.573Z
To be fair, I think it's only "clear" once you've seen the reduction :).
Joshua Grochow
CC BY-SA 3.0
2017-08-24T07:35:08.497Z
Right :) it requires to read the page where lemma 3 appears.
anps
CC BY-SA 3.0
2017-08-24T12:48:59.357Z
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.
Joshua Grochow
CC BY-SA 3.0
2017-12-21T19:05:56.307Z
@JoshuaGrochow It is not clear.
Turbo
CC BY-SA 3.0
2017-08-23T18:35:08.643Z
2017-08-23T18:35:08.643Z
anps
<p>I am interested in highly parallel algorithms for computing the determinant of matrices of a special form (over finite fields).</p>

<p>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.</p>

<p>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. </p>

<circuit-complexity><parallel>
parallel algorithms for the determinant of the Hessenberg matrix
anps
# parallel algorithms for the determinant of the Hessenberg matrix

(Asked by: username_0 on 2017-08-23)

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.

**Tags:** circuit-complexity, parallel

---

## 1 answers

### Answer by username_0 on 2017-08-23. Score: 3

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

> **Comments:**
> **username_1**: To be fair, I think it's only "clear" once you've seen the reduction :).  
> **username_0**: Right :) it requires to read the page where lemma 3 appears.  
> **username_1**: 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.  
> **username_2**: @JoshuaGrochow It is not clear.  

---

