期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
