2 citations · 3 across the 14 of their papers we have counts for
13 papers · 1 filter
Almost Optimal FPT Inapproximability for k-SetCover
Venkatesan Guruswami, Xuandi Ren
We show that -approximate parameterized -SetCover is W[1]-hard, and has no -time algorithms under ETH. This improves upon…
On the Approximability of Parameterized Minimum Monotone Satisfying Assignment
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +1
The parameterized Minimum Monotone Satisfying Assignment (-MMSA) problem asks whether a monotone Boolean circuit admits a satisfying assignment of Hamming weight at most . Th…
Strong Inapproximability for a Promise Rank Problem
Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang
Given a linear subspace of matrices over that is promised to contain a matrix of rank , we prove that it is hard to find a matrix of rank $n^{o(1/…
PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
Venkatesan Guruswami, Xuandi Ren, Kewen Wu
The Reconfiguration Inapproximability Hypothesis (RIH), recently established by Hirahara-Ohsaka (STOC'24) and Karthik-Manurangsi (ECCC'24), studies the hardness of reconfiguring on…
PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren
We give simple deterministic reductions demonstrating the NP-hardness of approximating the nearest codeword problem and minimum distance problem within arbitrary constant factors (…
Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices
Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee +1
Finding sparse vectors is a fundamental problem that arises in several contexts including codes, subspaces, and lattices. In this work, we prove strong inapproximability results fo…
Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts that, there is a constant such tha…
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…
Parameterized Inapproximability Hypothesis under ETH
Venkatesan Guruswami, Bingkai Lin, Xuandi Ren +2
The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the numb…
Baby PIH: Parameterized Inapproximability of Min CSP
Venkatesan Guruswami, Xuandi Ren, Sai Sandeep
The Parameterized Inapproximability Hypothesis (PIH) is the analog of the PCP theorem in the world of parameterized complexity. It asserts that no FPT algorithm can distinguish a s…
Improved Hardness of Approximating k-Clique under ETH
Bingkai Lin, Xuandi Ren, Yican Sun +1
In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no -time algorithm that can decide whether an -vertex gr…
A Survey on Parameterized Inapproximability: -Clique, -SetCover, and More
Xuandi Ren
In the past a few years, many interesting inapproximability results have been obtained from the parameterized perspective. This article surveys some of such results, with a focus o…
On Lower Bounds of Approximating Parameterized -Clique
Bingkai Lin, Xuandi Ren, Yican Sun +1
Given a simple graph and an integer , the goal of -Clique problem is to decide if contains a complete subgraph of size . We say an algorithm approximates -Cliqu…