The complexity-theory tag has no wiki summary.
15
votes
1answer
335 views
Implications of approximating the determinant
It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space.
What would be the complexity implications of approximating the determinant of a ...
6
votes
1answer
172 views
Are there applications of modular graph decomposition in TCS/complexity theory?
What are there some applications of modular graph decomposition in TCS/complexity theory?
I am especially interested in its use in proofs or upper/lower bounds if it occurs.
[1] Modular graph ...
