  In this work we advance the understanding of the fundamental limits of
computation for Binary Polynomial Optimization (BPO), which is the problem of
maximizing a given polynomial function over all binary points. In our main
result we provide a novel class of BPO that can be solved efficiently both from
a theoretical and computational perspective. In fact, we give a strongly
polynomial-time algorithm for instances whose corresponding hypergraph is
beta-acyclic. We note that the beta-acyclicity assumption is natural in several
applications including relational database schemes and the lifted multicut
problem on trees. Due to the novelty of our proving technique, we obtain an
algorithm which is interesting also from a practical viewpoint. This is because
our algorithm is very simple to implement and the running time is a polynomial
of very low degree in the number of nodes and edges of the hypergraph. Our
result completely settles the computational complexity of BPO over acyclic
hypergraphs, since the problem is NP-hard on alpha-acyclic instances. Our
algorithm can also be applied to any general BPO problem that contains
beta-cycles. For these problems, the algorithm returns a smaller instance
together with a rule to extend any optimal solution of the smaller instance to
an optimal solution of the original instance.
