7 citations · 22 across the 10 of their papers we have counts for
6 papers · 1 filter
On the number of integer points in translated and expanded polyhedra
Danny Nguyen, Igor Pak
We prove that the problem of minimizing the number of integer points inparallel translations of a rational convex polytope in is NP-hard. We apply this result to sho…
Short Presburger arithmetic is hard
Danny Nguyen, Igor Pak
We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short" we mean sentences with a bounded number of variables, quantifiers, ine…
Complexity of short Presburger arithmetic
Danny Nguyen, Igor Pak
We study complexity of short sentences in Presburger arithmetic (Short-PA). Here by "short" we mean sentences with a bounded number of variables, quantifiers, inequalities and Bool…
The computational complexity of integer programming with alternations
Danny Nguyen, Igor Pak
We prove that integer programming with three quantifier alternations is -complete, even for a fixed number of variables. This complements earlier results by Lenstra and Kannan,…
Complexity of short generating functions
Danny Nguyen, Igor Pak
We give complexity analysis of the class of short generating functions (GF). Assuming , we show that this class is not closed under taking many intersect…
Enumerating projections of integer points in unbounded polyhedra
Danny Nguyen, Igor Pak
We extend the Barvinok-Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra. For this, we obtain a new structural result on projections…