Abstract
Let P be a homogeneous polynomial of degree N in m variables. We assume that the polynomial is given as an exact evaluation oracle. Let S be a nontrivial subset of variables, S' is its compliment. Variables are S-separated if P(x1,..,xm) = Q(xi, i \in S) R(xj, j \in S'); monomials are S-splitted if deg(S) + deg(S') = N. In the homogeneous case S-separation implies S-splitting. Our main technical result states that if P is strongly log-concave on an open set then S-splitting implies S-separation. We show that deciding if there exists nontrivial S such that P is S-separable is in BPP, whereas S-splitting is NP-HARD in general. Thus our result gives poly-time randomized algorithm for S-splitting in strongly log-concave case. In the case of H-stable polynomials we present a poly-time deterministic algorithm.