3 citations · 8 across the 7 of their papers we have counts for
9 papers
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…
Obtaining Approximately Optimal and Diverse Solutions via Dispersion
Jie Gao, Mayank Goswami, Karthik C. S. +3
There has been a long-standing interest in computing diverse solutions to optimization problems. Motivated by reallocation of governmental institutions in Sweden, in 1995 J. Krarup…
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…
Communication Complexity of Correlated Equilibrium in Two-Player Games
Anat Ganor, Karthik C. S.
We show a communication complexity lower bound for finding a correlated equilibrium of a two-player game. More precisely, we define a two-player game called the 2-cycl…
Did the Train Reach its Destination: The Complexity of Finding a Witness
Karthik C. S.
Recently, Dohrau et al. studied a zero-player game on switch graphs and proved that deciding the termination of the game is in NP coNP. In this short paper, we show that the…
On the Complexity of Closest Pair via Polar-Pair of Point-Sets
Roee David, Karthik C. S., Bundit Laekhanukit
Every graph can be represented by a collection of equi-radii spheres in a -dimensional metric such that there is an edge in if and only if the spheres correspon…
On the Sensitivity Conjecture for Disjunctive Normal Forms
Karthik C. S., Sébastien Tavenas
The sensitivity conjecture of Nisan and Szegedy [CC '94] asks whether for any Boolean function , the maximum sensitivity , is polynomially related to its block sensitivity…