On hardness of computing analytic Brouwer degree
We prove that counting the analytic Brouwer degree of rational coefficient polynomial maps in Map(ℂ^d, ℂ^d) – presented in degree-coefficient form – is hard for the complexity class ♯ P, in the following sense: if there is a randomized polynomial time algorithm that counts the Brouwer degree correctly for a good fraction of all input instances (with coefficients of bounded height where the bound is an input to the algorithm), then P^♯ P =BPP.
READ FULL TEXT