For any epsilon > 0, we prove that k-Dimensional Matching is hard to approximate within a factor of k/(12 + epsilon) for large k unless NP subseteq 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 an Omega(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 Omega_k(R) using known randomised sparsification methods for CSPs.
Joint work with Ola Svensson and Theophile Thiery

Euiwoong Lee is an assistant professor at the University of Michigan. He got his Ph.D. from Carnegie Mellon University in 2017 and worked as a research fellow at the Simons Institute for the Theory of Computing at UC Berkeley and a postdoc at New York University. His research interests lie in several topics of theoretical computer science including approximation algorithms and hardness of approximation. His work has been recognized by several awards, including NSF CAREER Award, Edmund M. Clarke Dissertation Award, and ICALP Best Student Paper Award.