UCLA

A wide variety of problems in Discrete Optimization and Integer Programming can be naturally phrased in the language of Presburger Arithmetic (PA), which is the first order logic on the integers with only additions and inequalities. Understanding the exact computational complexity of PA is a classical topic in both logic and computer science. In this dissertation, we give answers to several open questions in this area.

Most important in PA are the numbers of variables and inequalities involved. The main question addressed in Part I of the dissertation is: By restricting the number of variables and inequalities in PA, do we obtain polynomial complexity? We give a negative solution to this, which also settles two questions by Kannan and Barvinok–Woods on Parametric Integer Programming and Short Presburger Arithmetic, respectively. Our argument combines elements from Number Theory and Discrete Geometry. As applications, we apply our tools to analyze the VC-dimensions of PA formulas, as well as a variant theory, called Parametric Presburger Arithmetic.

In Part II, we investigate the related theory of Short Generating Functions developed by Barvinok and Woods. First, we first extend their polynomial time algorithm for enumerating projected integer points in polytopes to the unbounded polyhedra case. Then we demon-

strate several limitations of their general theory under simple point set operations such as projection and union, in the sense that the lengths of the generating functions do not remain polynomially bounded. The reasoning here parallels with Part I, and crucially exploits the structures of PA definable sets.

In Part III, we present two different problems. The first one concerns an extension of PA with scalar multiplications by algebraic irrationals. We show that it has high nonelementary complexity far exceeding that of classical PA, even with a restricted number of variables and inequalities. The second problem is about minimizing the number of integer points in a polytope under translation. We show that it is NP-hard by embedding arbitrary polynomial functions as integer point counting functions of polytopes. We derive from this a consequence about the universality of Ehrhart quasi-polynomials.