  We study the $d$-dimensional knapsack problem. We are given a set of items,
each with a $d$-dimensional cost vector and a profit, along with a
$d$-dimensional budget vector. The goal is to select a set of items that do not
exceed the budget in all dimensions and maximize the total profit. A PTAS with
running time $n^{\Theta(d/\varepsilon)}$ has long been known for this problem,
where $\varepsilon$ is the error parameter and $n$ is the encoding size.
Despite decades of active research, the best running time of a PTAS has
remained $O(n^{\lceil d/\varepsilon \rceil - d})$. Unfortunately, existing
lower bounds only cover the special case with two dimensions $d = 2$, and do
not answer whether there is a $n^{o(d/\varepsilon)}$-time PTAS for larger
values of $d$. The status of exact algorithms is similar: there is a simple
$O(n \cdot W^d)$-time (exact) dynamic programming algorithm, where $W$ is the
maximum budget, but there is no lower bound which explains the strong
exponential dependence on $d$.
  In this work, we show that the running times of the best-known PTAS and exact
algorithm cannot be improved up to a polylogarithmic factor assuming Gap-ETH.
Our techniques are based on a robust reduction from 2-CSP, which embeds 2-CSP
constraints into a desired number of dimensions, exhibiting tight trade-off
between $d$ and $\varepsilon$ for most regimes of the parameters. Informally,
we obtain the following main results for $d$-dimensional knapsack.
  No $n^{o(d/\varepsilon \cdot 1/(\log(d/\varepsilon))^2)}$-time
$(1-\varepsilon)$-approximation for every $\varepsilon = O(1/\log d)$.
  No $(n+W)^{o(d/\log d)}$-time exact algorithm (assuming ETH).
  No $n^{o(\sqrt{d})}$-time $(1-\varepsilon)$-approximation for constant
$\varepsilon$.
  $(d \cdot \log W)^{O(d^2)} + n^{O(1)}$-time
$\Omega(1/\sqrt{d})$-approximation and a matching $n^{O(1)}$-time lower~bound.
