Asymptotically Optimal Hardness for k-Set Packing and k-Matroid Intersection

For any ε > 0, we prove that k-Dimensional Matching is hard to approximate within a factor of k/(12 + ε) for large k unless NP ⊆ BPP. Listed in Karp's 21 NP-complete problems, k-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: k-Set Packing, k-Matroid Intersection, and Matroid k-Parity. For all the aforementioned problems, the best known lower bound was a Ω(k/ log(k))-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieved an approximation of O(k). Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. The crux of our result hinges on a novel approximation preserving gadget from R-degree bounded k-CSPs over alphabet size R to kR-Dimensional Matching. Along the way, we prove that R-degree bounded k-CSPs over alphabet size R are hard to approximate within a factor Ω k (R) using known randomised sparsification methods for CSPs.