7 citations · 22 across the 10 of their papers we have counts for
11 papers
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…
Presburger Arithmetic with algebraic scalar multiplications
Philipp Hieronymi, Danny Nguyen, Igor Pak
We consider Presburger arithmetic (PA) extended by scalar multiplication by an algebraic irrational number , and call this extension -Presburger arithmetic (-PA). We show…
Parametric Presburger Arithmetic: Complexity of Counting and Quantifier Elimination
Tristram Bogart, John Goodrick, Danny Nguyen +1
We consider an expansion of Presburger arithmetic which allows multiplication by parameters . A formula in this language defines a parametric set $S_\mathbf{t}…
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…
The inverse moment problem for convex polytopes: implementation aspects
Nick Gravin, Danny Nguyen, Dmitrii Pasechnik +1
We give a detailed technical report on the implementation of the algorithm presented in Gravin et al. (Discrete & Computational Geometry'12) for reconstructing an -vertex convex…
Tiling the integer lattice with translated sublattices
Maciej Borodzik, Danny Nguyen, Sinai Robins
When is represented as a finite disjoint union of translated integer sublattices, the translated sublattices must possess some special properties. Such a representat…
Solid angles associated to Minkowski reduced bases
Danny Nguyen
Given a lattice , we consider its Minkowski reduced basis and the solid angle spanned by the basis vectors. Such a basis satisfies strong near-orthogonal…