Xuandi Ren

Research

  • As an undergraduate, I collaborated with Prof. Bingkai Lin on Parameterized Inapproximability, with Prof. Huacheng Yu on Sketching Complexity, and with Prof. Pinyan Lu on Algorithms with Predictions.

  • During my Ph.D., my research has focused primarily on Hardness of Approximation.

  • More recently, I have become interested in exploring large language models. From June 2025 to August 2026, I was interning at ByteDance Seed as a student researcher.

Publications

(Unless stated otherwise, authors are sorted in alphabetical order)

  • Inapproximability of Unique-Machine Precedence Scheduling for Unit-Length Jobs.
    Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang.
    Preprint. [arxiv]

  • On the Approximability of Parameterized Minimum Monotone Satisfying Assignment.
    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Xin Zheng.
    APPROX 2026. [arxiv] [slides]

  • Strong Inapproximability for a Promise Rank Problem.
    Venkatesan Guruswami, Xuandi Ren, Shaoxuan Tang.
    APPROX 2026. [arxiv] [slides]

  • Brief Announcement: Scheduling Problems with Constrained Rejections.
    Sami Davies, Venkatesan Guruswami, Xuandi Ren.
    SPAA 2026. [arxiv]

  • On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results.
    Venkatesan Guruswami, Karthik C. S., Pasin Manurangsi, Xuandi Ren, Kewen Wu.
    Preprint. [arxiv] (Merged from [KM24] and [GRW25])

  • Inapproximability of Finding Sparse Vectors in Codes, Subspaces, and Lattices.
    Vijay Bhattiprolu, Venkatesan Guruswami, Euiwoong Lee, Xuandi Ren.
    FOCS 2025. [arxiv]

  • Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.
    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu.
    STOC 2025. [arxiv] [slides]

  • Baby PIH: Parameterized Inapproximability of Min CSP.
    Venkatesan Guruswami, Xuandi Ren, Sai Sandeep.
    CCC 2024 and Computational Complexity, Vol. 35, Article 8. [arxiv] [journal] [slides]

  • Parameterized Inapproximability Hypothesis under ETH.
    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu.
    STOC 2024 (Best Paper Award) and Journal of the ACM, Vol. 72, No. 5, Article 32. [arxiv] [journal] [slides]

  • Improved Hardness of Approximating k-Clique under ETH.
    Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang.
    FOCS 2023. [arxiv] [slides]

  • Constant Approximating Parameterized k-SetCover is W[2]-hard.
    Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang.
    SODA 2023. [arxiv] [slides]

  • On Lower Bounds of Approximating Parameterized k-Clique.
    Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang.
    ICALP 2022. [arxiv] [slides]

  • Generalized Sorting with Predictions.
    Pinyan Lu, Xuandi Ren, Enze Sun, Yubo Zhang.
    SOSA 2021. [arxiv] [slides]