Computer Science Colloquium

In this talk we survey the close connection between the solution set of a finite system of linear Diophantine equations and semilinear sets. Linear sets generalize arithmetic progressions to several dimensions. The closure under union of the linear sets yields the semilinear sets, which by a kind of miracle are closed under all Boolean operations. We give a high-level, conceptually transparent algorithm that reveals both the structure of the solution set of a system of linear Diophantine equations and its computational complexity. Along the way we also point out an important connection between the set of support of multivariate rational series and general Diophantine polynomials.

Bruce Litow is a senior lecturer in the School of IT. His principal research interest is the computational complexity of arithmetic and algebraic problems.