Publications

Vijay Bhattiprolu, Venkatesan Guruswami, Xuandi Ren (2025). PCP-free APX-Hardness of Nearest Codeword and Minimum Distance. Preprint.

arxiv eccc

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu (2025). Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH. Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.

arxiv eccc

Venkatesan Guruswami, Xuandi Ren, Sai Sandeep (2024). Baby PIH: Parameterized Inapproximability of Min CSP. 39th Computational Complexity Conference (CCC), 2024.

arxiv eccc slides

Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu (2024). Parameterized Inapproximability Hypothesis under ETH. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024, (Best Paper Award).

arxiv eccc slides

Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang (2023). Improved Hardness of Approximating k-Clique under ETH. Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2023.

arxiv slides

Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang (2023). Constant Approximating Parameterized k-SetCover is W[2]-hard. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

arxiv slides

Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang (2022). On Lower Bounds of Approximating Parameterized k-Clique. Proceedings of the 49th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2022.

arxiv slides

Pinyan Lu, Xuandi Ren, Enze Sun, Yubo Zhang (2021). Generalized Sorting with Predictions. Proceedings of the 4th Symposium on Simplicity in Algorithms (SOSA), 2021.

arxiv slides