Author name cluster

Xuandi Ren

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers

1 author row

STOC Conference 2025 Conference Paper

Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH

Venkatesan Guruswami
Bingkai Lin
Xuandi Ren
Yican Sun
Kewen Wu 0001

The Parameterized Inapproximability Hypothesis (PIH), which is an analog of the PCP theorem in parameterized complexity, asserts the following: there is a constant ε> 0 such that for any computable function f :ℕ→ℕ, no f ( k )· n O (1) -time algorithm can, on input a k -variable CSP instance with domain size n , find an assignment satisfying 1−ε fraction of the constraints. A recent work by Guruswami, Lin, Ren, Sun, and Wu (STOC’24) established PIH under the Exponential Time Hypothesis (ETH). In this work, we improve the quantitative aspects of PIH and prove (under ETH) that approximating sparse parameterized CSPs within a constant factor requires n k 1− o (1) time. This immediately implies, for example, that finding a ( k /2)-clique in an n -vertex graph with a k -clique requires n k 1− o (1) time (assuming ETH). We also prove almost optimal time lower bounds for approximating k -ExactCover and Max k -Coverage. Our proof follows the blueprint of the previous work to identify a ”vector-structured” ETH-hard CSP whose satisfiability can be checked via an appropriate form of ”parallel” PCP. Using further ideas in the reduction, we guarantee additional structures for constraints in the CSP. We then leverage this to design a parallel PCP of almost linear size based on Reed-Muller codes and derandomized low degree testing.

Details

FOCS Conference 2025 Conference Paper

Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices

Vijay Bhattiprolu
Venkatesan Guruswami
Euiwoong Lee
Xuandi Ren

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 for all these variants using a novel approach that even bypasses the PCP theorem. Our main result is that it is NP-hard (under randomized reductions) to approximate the sparsest vector in a real subspace within any constant factor; the gap can be further amplified using tensoring. Our reduction has the property that there is a Boolean solution in the completeness case. As a corollary, this immediately recovers the state-of-the-art inapproximability factors for the shortest vector problem (SVP) on lattices. Our proof extends the range of $\mathbf{l}_{\_} \mathbf{p}$ (quasi) norms for which hardness was previously known, from ‘p at least one’ to ‘p at least zero’, answering a question raised by (Khot, JACM 2005). Previous hardness results for SVP, and the related minimum distance problem (MDP) for error-correcting codes, all use lattice/coding gadgets that have an abundance of codewords in a ball of radius smaller than the minimum distance. In contrast, our reduction only needs many codewords in a ball of radius slightly larger than the minimum distance. This enables an easy derandomization of our reduction for finite fields, giving a new elementary proof of deterministic hardness for MDP. We believe this weaker density requirement might offer a promising approach to showing deterministic hardness of SVP, a long elusive goal. The key technical ingredient underlying our result for real subspaces is a proof that in the kernel of a random Rademacher matrix, the support of any two linearly independent vectors have very little overlap. A broader motivation behind this work is the development of inapproximability techniques for problems over the reals. Analytic variants of sparsest vector have connections to small set expansion, quantum separability and polynomial maximization over convex sets, all of which appear to be out of reach of current PCP techniques. We hope that the approach we develop could enable progress on some of these problems.

Details

STOC Conference 2024 Conference Paper

Parameterized Inapproximability Hypothesis under Exponential Time Hypothesis

Venkatesan Guruswami
Bingkai Lin
Xuandi Ren
Yican Sun
Kewen Wu 0001

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an ε fraction of constraints for some absolute constant ε > 0. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap. In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a “parallel PCP of proximity” based on the Walsh-Hadamard code.

Details

SODA Conference 2023 Conference Paper

Constant Approximating Parameterized k -SETCOVER is W[2]-hard

Bingkai Lin
Xuandi Ren
Yican Sun
Xiuhan Wang

In this paper, we prove that it is W[2]-hard to approximate k-SETCOVER within any constant ratio. Our proof is built upon the recently developed threshold graph composition technique. We propose a strong notion of threshold graphs and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time ratio approximation algorithms for the non-parameterized k -SETCOVER problem with k as small as, assuming W[1] ≠ FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.

Details

FOCS Conference 2023 Conference Paper

Improved Hardness of Approximating k-Clique under ETH

Bingkai Lin
Xuandi Ren
Yican Sun
Xiuhan Wang

In this paper, we prove that assuming the exponential time hypothesis (ETH), there is no $f(k) \cdot n^{k^{o(1 / \log \log k)}}$-time algorithm that can decide whether an n-vertex graph contains a clique of size k or contains no clique of size $k / 2$, and no FPT algorithm can decide whether an input graph has a clique of size k or no clique of size $k / f(k)$, where $f(k)$ is some function in $k^{1-o(1)}$. Our results significantly improve the previous works [1], [2]. The crux of our proof is a framework to construct gap-producing reductions for the k-CLIQUE problem. More precisely, we show that given an error-correcting code $C: \Sigma_{1}^{k} \rightarrow \Sigma_{2}^{k^{\prime}}$ that is locally testable and smooth locally decodable in the parallel setting, one can construct a reduction which on input a graph G outputs a graph $G^{\prime}$ in $\left(k^{\prime}\right)^{O(1)} \cdot n^{O\left(\log \left|\Sigma_{2}\right| / \log \left|\Sigma_{1}\right|\right)}$ time such•if G has a clique of size k, then $G^{\prime}$ has a clique of size K, where $K=\left(k^{\prime}\right)^{O(1)}$. •if G has no clique of size k, then $G^{\prime}$ has no clique of size $(1-\varepsilon) \cdot K$ for some constant $\varepsilon \in(0, 1)$. We then construct such a code with $k^{\prime}=k^{\Theta(\log \log k)}$ and $\left|\Sigma_{2}\right|=\left|\Sigma_{1}\right|^{k^{0. 54}}$, establishing the hardness result above. Our code generalizes the derivative code [3] into the case with a super constant order of derivatives.

Details