In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.