In a seminal paper, Kannan and Lovász (1988) considered a quantity KL(Λ,K) which
denotes the best volume-based lower bound on the covering radius μ(Λ,K) of a convex body …

We give a novel algorithm for enumerating lattice points in any convex body, and give
applications to several classic lattice problems, including the Shortest and Closest Vector …

A Reverse Minkowski Theorem Page 1 A Reverse Minkowski Theorem Oded Regev ∗
Courant Institute, New York University New York, New York 10012, United States Noah …

Multidimensional packing problems generalize the classical packing problems such as Bin
Packing, Multiprocessor Scheduling by allowing the jobs to be d-dimensional vectors. While …

Let P be a set of n points in Euclidean space and let 0< ε< 1. A well-known result of Johnson
and Lindenstrauss states that there is a projection of P onto a subspace of dimension O(ϵ …

We consider integer programming problems $\max\{c^ T x:\mathcal {A} x= b, l\leq x\leq u,
x\in\mathbb {Z}^{nt}\} $ where $\mathcal {A} $ has a (recursive) block-structure generalizing" …

We present randomized algorithms that solve subset sum and knapsack instances with n
items in O^*(2^0.86n) time, where the O^*(⋅) notation suppresses factors polynomial in the …

The theory of $ n $-fold integer programming has been recently emerging as an important
tool in parameterized complexity. The input to an $ n $-fold integer program (IP) consists of …

The maximum volume j-simplex problem asks to compute the j-dimensional simplex of
maximum volume inside the convex hull of a given set of n points in Qd. We give a …

Let L be a lattice in ℝ n and K a convex body disjoint from L. The classical Flatness Theorem
asserts that then w (K, L), the L-width of K, does not exceed some bound, depending only on …