Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Thanh Minh Hoang:

TR10-194 | 9th December 2010
Thanh Minh Hoang

Isolation of Matchings via Chinese Remaindering

In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme
using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT
suggested by Agrawal in a CCC'03-paper
for testing perfect matchings. We show that ... more >>>

TR09-091 | 23rd September 2009
Thanh Minh Hoang

On the Matching Problem for Special Graph Classes

Revisions: 1

In the present paper we show some new complexity bounds for
the matching problem for special graph classes.
We show that for graphs with a polynomially bounded number
of nice cycles, the decision perfect matching problem is in
$SPL$, it is hard for $FewL$, and the construction ... more >>>

TR06-129 | 6th October 2006
Manindra Agrawal, Thanh Minh Hoang, Thomas Thierauf

The polynomially bounded perfect matching problem is in NC^2

The perfect matching problem is known to
be in P, in randomized NC, and it is hard for NL.
Whether the perfect matching problem is in NC is one of
the most prominent open questions in complexity
theory regarding parallel computations.

Grigoriev and Karpinski studied the perfect matching problem
more >>>

TR04-024 | 26th March 2004
Thomas Thierauf, Thanh Minh Hoang

On Closure Properties of GapL

Revisions: 1 , Comments: 1

We show necessary and sufficient conditions that
certain algebraic functions like the rank or the signature
of an integer matrix can be computed in GapL.

more >>>

TR01-028 | 16th March 2001
Thanh Minh Hoang, Thomas Thierauf

The Complexity of the Minimal Polynomial

We investigate the computational complexity
of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial
is in AC^0(GapL), the AC^0-closure of the logspace
counting class GapL, which is contained in NC^2.
Our main result is that the problem is hard ... more >>>

ISSN 1433-8092 | Imprint