Showing 2024Show all
2 papers · 1 filter
cs.CC2024
On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
Karthik C. S., Euiwoong Lee, Pasin Manurangsi
Parameterized Inapproximability Hypothesis (PIH) is a central question in the field of parameterized complexity. PIH asserts that given as input a 2-CSP on variables and alphab…
cs.IT2024
Explicit Good Codes Approaching Distance 1 in Ulam Metric
Elazar Goldenberg, Mursalin Habib, Karthik C. S
The Ulam distance of two permutations on is minus the length of their longest common subsequence. In this paper, we show that for every , there exists some…