Showing cs.CCShow all
2 papers · 1 filter
cs.CC2023
Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
Karthik C. S., Dániel Marx, Marcin Pilipczuk +1
Assuming the Exponential Time Hypothesis (ETH), a result of Marx (ToC'10) implies that there is no time algorithm that can solve 2-CSPs with constra…
cs.CC2020
On Hardness of Approximation of Parameterized Set Cover and Label Cover: Threshold Graphs from Error Correcting Codes
Karthik C. S., Inbal Livni-Navon
In the -SetCover problem, we are given a collection of sets over a universe , and the goal is to distinguish between the case that contains $k…