3 citations · 3 across the 2 of their papers we have counts for
4 papers · 1 filter
Improved Multilayered PCPs and Hypergraph Vertex Cover
Karthik C. S., Dor Minzer
We present two elementary constructions of multilayered PCPs that improve upon prior constructions in two ways. Specifically, we give one construction of quasi-linear size, and ano…
On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi +2
Recently, Ohsaka [STACS'23] put forth the Reconfiguration Inapproximability Hypothesis (RIH), which roughly asserts that there is some such that given as input a -CSP inst…
Hardness Amplification of Optimization Problems
Elazar Goldenberg, Karthik C. S.
In this paper, we prove a general hardness amplification scheme for optimization problems based on the technique of direct products. We say that an optimization problem is dire…
Parameterized Intractability of Even Set and Shortest Vector Problem from Gap-ETH
Arnab Bhattacharyya, Suprovat Ghoshal, Karthik C. S. +1
The -Even Set problem is a parameterized variant of the Minimum Distance Problem of linear codes over , which can be stated as follows: given a generator matrix $\m…