  In binary polynomial optimization, the goal is to find a binary point
maximizing a given polynomial function. In this paper, we propose a novel way
of formulating this general optimization problem, which we call factorized
binary polynomial optimization. In this formulation, we assume that the
variables are partitioned into a fixed number of sets, and that the objective
function is written as a sum of r products of linear functions, each one
involving only variables in one set of the partition. Our main result is an
algorithm that solves factorized binary polynomial optimization in strongly
polynomial time, when r is fixed. This result provides a vast new class of
tractable instances of binary polynomial optimization, and it even improves on
the state-of-the-art for quadratic objective functions, both in terms of
generality and running time. We demonstrate the applicability of our result
through the binary tensor factorization problem, which arises in mining
discrete patterns in data, and that contains as a special case the rank-1
Boolean tensor factorization problem. Our main result implies that these
problems can be solved in strongly polynomial time, if the input tensor has
fixed rank, and a rank factorization is given. For the rank-1 Boolean matrix
factorization problem, we only require that the input matrix has fixed rank.
