A sum of affine powers is an expression of the form [f(x1,...,xn) = ∑i=1s αi li(x1,...,xn)ei] where li is an affine form. We propose polynomial time black-box algorithms that find the decomposition with the smallest value of s for an input polynomial f . Our algorithms work in situations where s is small enough compared to the number of variables or to the exponents ei. Although quite simple, this model is a generalization of Waring decomposition. This paper extends previous work on Waring decomposition as well as our work on univariate sums of affine powers (ISSAC'17).

A sum of affine powers is an expression of the form f(x) = s∑/i=1 αi (x - ai)ei. Although quite simple, this model is a generalization of two well-studied models: Waring decomposition and Sparsest Shift. For these three models there are natural extensions to several variables, but this paper is mostly focused on univariate polynomials. We propose algorithms that find the smallest decomposition of f in the first model (sums of affine powers) for an input polynomial f given in dense representation. Our algorithms only work in situations where the smallest decomposition is unique, and we provide conditions that guarantee the uniqueness of the smallest decomposition.

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.

In this paper, we investigate three problems concerning the toric ideal associated to a matroid. First, we list all matroids $\mathcal{M}$ such that its corresponding toric ideal $I_{\mathcal{M}}$ is a complete intersection. Second, we handle the problem of detecting minors of a matroid $\mathcal{M}$ from a minimal set of binomial generators of $I_{\mathcal{M}}$. In particular, given a minimal set of binomial generators of $I_{\mathcal{M}}$ we provide a necessary condition for $\mathcal{M}$ to have a minor isomorphic to $\mathcal{U}_{d,2d}$ for $d \geq 2$. This condition is proved to be sufficient for $d = 2$ (leading to a criterion for determining whether $\mathcal{M}$ is binary) and for $d = 3$. Finally, we characterize all matroids $\mathcal{M}$ such that $I_{\mathcal{M}}$ has a unique minimal set of binomial generators.