\({\sf D}k{\sf S}\)  and \({\sf D}k{\sf SH}\) . There is a long line of works which study the complexity of approximating \({\sf D}k{\sf S}\) . Feige [1]} showed constant \({\sf D}k{\sf S}\)  is -hard assuming the hardness of refuting random 3-SAT formulas. Subsequently Khot [2]} also established -hardness assuming no sub-exponential time algorithms exist for SAT. Stronger inapproximability results are known under alternative hypotheses. The SSEH of Raghavendra and Steurer [3]} immediately implies constant factor inapproximability of \({\sf D}k{\sf S}\)  where as Manurangsi [4]} showed almost polynomial ratio ETH based hardness. There are also results which establish running time lower bounds under alternative hypotheses [5]},[6]}. On the algorithmic front, Feige and Seltser [7]} give a \(n/k\) -approximation algorithm for \({\sf D}k{\sf S}\) . For \(k\) -independent bounds, Fiege, Kortsarz and Peleg [8]} gave a \(n^{1/3 - \epsilon }\)  -approximation algorithm, which was later improved to a \(n^{1/4 + \epsilon }\)  by [9]}. In comparison, there have been relatively fewer works which study the hypergraph variant i.e., \({\sf D}k{\sf SH}\) . Assuming the existence of certain one way functions, Applebaum [10]} showed that \({\sf D}k{\sf SH}\)  is hard to approximate for hypergraphs on \(n\) -vertices up to a factor of \(n^\epsilon \) , for some constant \(\epsilon > 0\) . The results of [11]} also implies that assuming SSEH, \({\sf D}k{\sf SH}\)  is inapproximable for any constant factor with large enough arity.
