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.

Publications

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

  • Scheduling Problems with Constrained Rejections.
    Sami Davies, Venkatesan Guruswami, Xuandi Ren.
    Preprint, 2025.

  • PCPP-Based Reconfiguration Inapproximability: Soundness Gap and Query Complexity Trade-offs.
    Venkatesan Guruswami, Xuandi Ren, Kewen Wu.
    Preprint, 2025.

  • PCP-free APX-Hardness of Nearest Codeword and Minimum Distance.
    Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren.
    Preprint, 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.
    Symposium on Theory of Computing (STOC), 2025. [arxiv]

  • Baby PIH: Parameterized Inapproximability of Min CSP.
    Venkatesan Guruswami, Xuandi Ren, Sai Sandeep.
    Computational Complexity Conference (CCC), 2024. [arxiv] [slides]

  • Parameterized Inapproximability Hypothesis under ETH.
    Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu.
    Symposium on Theory of Computing (STOC), 2024 (Best Paper Award). [arxiv] [slides]

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

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

  • On Lower Bounds of Approximating Parameterized k-Clique.
    Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang.
    International Colloquium on Automata, Languages and Programming (ICALP), 2022. [arxiv] [slides]

  • Generalized Sorting with Predictions.
    Pinyan Lu, Xuandi Ren, Enze Sun, Yubo Zhang.
    Symposium on Simplicity in Algorithms (SOSA), 2021. [arxiv] [slides]