The Computational Complexity of Integer Programming with Alternations

References

• [1] Arora S, Barak B (2009) Computational Complexity: A Modern Approach (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [2] Barvinok A (1993) A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Proc. 34th Foundations Comput. Sci. (IEEE Computer Society, Los Alamitos, CA), 566–572.Crossref, Google Scholar
• [3] Barvinok A (2008) Integer Points in Polyhedra (European Mathematical Society, Zürich).Crossref, Google Scholar
• [4] Barvinok A, Pommersheim JE (1999) An algorithmic theory of lattice points in polyhedra. Billera LJ, Björner A, Green C, Simion R, Stanley RP, eds. New Perspectives in Algebraic Combinatorics (Cambridge University Press, Cambridge, UK), 91–147.Google Scholar
• [5] Barvinok A, Woods K (2003) Short rational generating functions for lattice point problems. J. Amer. Math. Soc. 16(4):957–979.Crossref, Google Scholar
• [6] De Loera JA, Rambau J, Santos F (2010) Triangulations (Springer, Berlin).Crossref, Google Scholar
• [7] Eisenbrand F (2010) Integer programming and algorithmic geometry of numbers. Jünger M, Liebling TM, Naddef D, Nemhauser GL, Pulleyblank WR, Reinelt G, Rinaldi G, Wolsey LA, eds. 50 years of Integer Programming (Springer, Berlin), 505–560.Crossref, Google Scholar
• [8] Eisenbrand F, Hähnle N (2012) Minimizing the number of lattice points in a translated polygon. Proc. 24th ACM/SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1123–1130.Google Scholar
• [9] Eisenbrand F, Rothvoß T (2009) New hardness results for Diophantine approximation. Dinur I, Jansen K, Naor J, Rolim J, eds. Approximation, Randomization, and Combinatorial Optimization—Algorithms and Techniques, Lecture Notes in Computer Science, vol. 5687 (Springer, Berlin), 98–110.Crossref, Google Scholar
• [10] Grädel E (1987) The complexity of subclasses of logical theories. PhD thesis, Universität Basel, Basel, Switzerland.Google Scholar
• [11] Grädel E (1988) Subclasses of Presburger arithmetic and the polynomial-time hierarchy. Theoret. Comput. Sci. 56(3):289–301.Crossref, Google Scholar
• [12] Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization (Springer, Berlin).Crossref, Google Scholar
• [13] Kannan R (1990) Test sets for integer programs, ∀ ∃ sentences. Cook W, Seymour PD, eds. Polyhedral Combinatorics (American Mathematical Society, Providence, RI), 39–47.Google Scholar
• [14] Kannan R (1992) Lattice translates of a polytope and the Frobenius problem. Combinatorica 12(2):161–177.Crossref, Google Scholar
• [15] Lagarias JC (1985) The computational complexity of simultaneous Diophantine approximation problems. SIAM J. Comput. 14(1):196–209.Crossref, Google Scholar
• [16] Lenstra H (1983) Integer programming with a fixed number of variables. Math. Oper. Res. 8(4):538–548.Link, Google Scholar
• [17] Moore C, Mertens S (2011) The Nature of Computation (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• [18] Nguyen D, Pak I (2017) Complexity of short Presburger arithmetic. Proc. 49th Sympos. Theory Comput. (Association for Computing Machinery, New York), 812–820.Crossref, Google Scholar
• [19] Nguyen D, Pak I (2018) Complexity of short generating functions. Forum Math., Sigma 6:e1.Crossref, Google Scholar
• [20] Papadimitriou CH (1994) Computational Complexity (Addison-Wesley, Reading, MA).Google Scholar
• [21] Schöning U (1997) Complexity of Presburger arithmetic with fixed quantifier dimension. Theory Comput. Systems 30(4):423–428.Crossref, Google Scholar
• [22] Schrijver A (1986) Theory of Linear and Integer Programming (Wiley, Chichester, UK).Google Scholar
• [23] van Emde Boas P (1981) Another NP-complete partition problem and the complexity of computing short vectors in a lattice. Report 81–04, Mathematics Department, University of Amsterdam, Amsterdam.Google Scholar
• [24] Woods K (2004) Rational generating functions and lattice point sets. Unpublished doctoral dissertation, University of Michigan, Ann Arbor.Google Scholar
• [25] Woods K (2015) Presburger arithmetic, rational generating functions, and quasi-polynomials. J. Symbolic Logic 80(2):433–449.Crossref, Google Scholar