Detecting Points in Integer Cones of Polytopes is Double-Exponentially Hard

Let d be a positive integer. For a finite set X ⊆ R ^d, we define its integer cone as the set IntCone(X):= { ^P _x∈ _X λx · x | λx ∈ Z _>0 } ⊆ R ^d. Goemans and Rothvoss showed that, given two polytopes P, Q ⊆ R ^d with P being bounded, one can decide whether IntCone(P ∩ Z ^d) intersects Q in time enc(P) ^2O(d) · enc(Q) ^O(1) [J. ACM 2020], where enc(·) denotes the number of bits required to encode a polytope through a system of linear inequalities. This result is the cornerstone of their XP algorithm for Bin Packing parameterized by the number of different item sizes. We complement their result by providing a conditional lower bound. In particular, we prove that, unless the ETH fails, there is no algorithm which, given a bounded polytope P ⊆ R ^d and a point q ∈ Z ^d, decides whether q ∈ IntCone(P ∩ Z ^d) in time enc(P, q) ^2o(d) . Note that this does not rule out the existence of a fixed-parameter tractable algorithm for the problem, but shows that dependence of the running time on the parameter d must be at least doubly-exponential.