  The method of partial derivatives is one of the most successful lower bound
methods for arithmetic circuits. It uses as a complexity measure the dimension
of the span of the partial derivatives of a polynomial. In this paper, we
consider this complexity measure as a computational problem: for an input
polynomial given as the sum of its nonzero monomials, what is the complexity of
computing the dimension of its space of partial derivatives? We show that this
problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace
method", recently used in combinatorics and in algebraic complexity to lower
bound the rank of certain matrices. We show that this method provides a
polynomial-time computable lower bound on the dimension of the span of partial
derivatives, and from this method we derive closed-form lower bounds. We leave
as an open problem the existence of an approximation algorithm with reasonable
performance guarantees.A slightly shorter version of this paper was presented
at STACS'17. In this new version we have corrected a typo in Section 4.1, and
added a reference to Shitov's work on tensor rank.
