Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-088 | 28th November 2000 00:00

A note on the hardness of the characteristic polynomial


Authors: Meena Mahajan, V. Vinay
Publication: 30th November 2000 10:26
Downloads: 1572


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

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.

ISSN 1433-8092 | Imprint