We prove that SVPp is NP-hard to approximate within a factor of 2log1 − ε n, for all constants ε > 0 and p > 2, under standard deterministic Karp reductions. This result is also the first proof that exact SVPp is NP-hard in a finite ℓp norm. Hardness for SVPp with p finite was previously only known if NP ⊈ RP, and under that assumption, hardness of approximation was only known for all constant factors. As a corollary to our main theorem, we show that under the Sliding Scale Conjecture, SVPp is NP-hard to approximate within a small polynomial factor, for all constants p > 2.

We revisit a standard polygon containment problem: given a convex $k$-gon $P$ and a convex $n$-gon $Q$ in the plane, find a placement of $P$ inside $Q$ under translation and rotation (if it exists), or more generally, find the largest copy of $P$ inside $Q$ under translation, rotation, and scaling. Previous algorithms by Chazelle (1983), Sharir and Toledo (1994), and Agarwal, Amenta, and Sharir (1998) all required $Ω(n^2)$ time, even in the simplest $k=3$ case. We present a significantly faster new algorithm for $k=3$ achieving $O(n$polylog $n)$ running time. Moreover, we extend the result for general $k$, achieving $O(k^{O(1/\varepsilon)}n^{1+\varepsilon})$ running time for any $\varepsilon>0$. Along the way, we also prove a new $O(k^{O(1)}n$polylog $n)$ bound on the number of similar copies of $P$ inside $Q$ that have 4 vertices of $P$ in contact with the boundary of $Q$ (assuming general position input), disproving a conjecture by Agarwal, Amenta, and Sharir (1998).

Data movement is a hot-button topic today, with workloads like machine learning (ML) training, graph processing, and data analytics consuming datasets as large as 30PB. Such a dataset would take almost a week to transfer at 400 gbps while consuming megajoules of energy just to operate the two endpoints’ optical transceivers. All of this time and energy is seen as an unavoidable overhead on top of directly accessing the disks that store the data. In this paper, we re-evaluate the fundamental assumption of networked data copying and instead propose the adoption of embodied data movement. Our insight is that solid state disks (SSDs) have been rapidly growing in an under-exploited way: their data density, both in TB per unit volume and unit mass. With data centres reaching kilometres in length, we propose a new architecture featuring data centre hyperloops2(DHLs) where large datasets, stored on commodity SSDs, are moved via magnetic levitation in low-pressure tubes. By eliminating much of the potential friction inherent to embodied data movement, DHLs offer more efficient data movement, with SSDs potentially travelling at hundreds of metres per second. Consequently, a contemporary dataset can be moved through a DHL in seconds and then accessed with local latency and bandwidth well into the terabytes per second. DHLs have the potential to massively reduce the network bandwidth and energy consumption associated with moving large datasets, but raise a variety of questions regarding the viability of their realisation and deployment. Through flexibility and creative engineering, we argue that many potential issues can be resolved. Further, we present models of DHLs and their application to workloads with growing data movement demands, such as training machine learning algorithms, large-scale physics experiments, and data centre backups. For a fixed data movement task, we obtain energy reductions of $1.6 \times$ to $376.1 \times$ and time speedups from $114.8 \times$ to $646.4 \times$ versus 400gbps optical networking. When modelling DHL in simulation, we obtain time speedups of between $5.7 \times$ and $118 \times$ (iso-power) and communication power reductions of between $6.4 \times$ and $135 \times$ (iso-time) to train an iteration of a representative DLRM workload. We provide a cost analysis, showing that DHLs are financially practical. With the scale of the improvements realisable through DHLs, we consider this paper a call to action for our community to grapple with the remaining architectural challenges.2HyperLoopTMis a term for high-speed transportation using magnetic levitation trains and low-pressure tubes; it does not imply a loop topology.