At the very origin of Algebraic Statistics was the 1998 theorem byDiaconis and Sturmfels showing the existence of Markov bases. They introduced a new sampling algorithm for a broad class of problems, showing how to explicitly construct a Markov chain over the support of the conditional distribution given the log-linear exponential family’s sufficient statistic. The chain is built using combinatorial moves that have analogues in polynomial algebra and polyhedral geometry. Each instance inherits a finite set of moves necessary to obtain an irreducible Markov chain for any value of the sufficient statistic. This has been applied for example in the context of contingency tables. After 25 years of this influencial work this talk discusses what we do not know about the complexity and structure of Markov bases and new applications in machine learning. All new results are joint work with Felix Almendra Hernandez and Sonja Petrovic and with Yue Wu.