The general asymmetric (and metric) TSP is known to be approximable
only to within an O(log n) factor, and is also known to be
approximable within a constant factor as soon as the metric is
bounded. In this paper we study the asymmetric and symmetric TSP
problems with bounded metrics ... more >>>

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, ... more >>>

We show that an LK proof of size $m$ of a monotone sequent (a sequent

that contains only formulas in the basis $\wedge,\vee$) can be turned

into a proof containing only monotone formulas of size $m^{O(\log m)}$

and with the number of proof lines polynomial in $m$. Also we show

... more >>>