TR00-088 Authors: Meena Mahajan, V. Vinay

Publication: 30th November 2000 10:26

Downloads: 1572

Keywords:

In this note, we consider the problem of computing the

coefficients of the characteristic polynomial of a given

matrix, and the related problem of verifying the

coefficents.

Santha and Tan [CC98] show that verifying the determinant

(the constant term in the characteristic polynomial) is

complete for the class C=L, and ask whether verification

becomes easier if all coefficients are given. Hoang and

Thierauf [CCC00] answer this negatively; they show that

verifying all coefficients is also complete for C=L. One of

our main contributions here is a considerably simplified

proof of this latter result. Our simplified proof is

combinatorial, as opposed to the algebraic proof of HT.

It is well known [Damm, Toda, Vinay, Valiant] that computing

the determinant i.e.\ the constant term of the

characteristic polynomial is hard for \gapl. On the other

hand, the coefficients of high degree terms are trivial or

easy to compute. Thus one may ask the question as to how

many coefficients are easy to compute. We partially answer

this question by showing that, for an n x n matrix:

1. For constant k, computing the coefficient of x^{n-k}

is in TC_0.

2. For constant c and for k in O((\log n)^c),

the coefficient of x^{n-k} can be computed by

polynomial size threshold circuits of O(\log \log n) depth.

3. For any fixed 0 < \epsilon \le 1, computing the

coefficient of x^{n-n^{\epsilon}} is hard for

GapL. Verifying it is hard for C=L.