Xuandi Ren

Xuandi Ren

Ph.D Candidate in Computer Science

University of California, Berkeley

Biography

I am a second-year Ph.D student in the theory group of UC Berkeley, where I’m very lucky to be advised by Venkatesan Guruswami.

I have a broad interest in theoretical computer science, especially in Computational Complexity and Hardness of Approximation.

During my undergrad, I was fortunate to work with Prof. Bingkai Lin on Parameterized Inapproximability, with Prof. Huacheng Yu on Sketching Complexity, and with Prof. Pinyan Lu on Algorithms with Predictions.

Email: xuandi_ren@berkeley.edu

Interests
  • Algorithms
  • Parameterized Complexity
  • Hardness of Approximation
Education
  • PhD in Computer Science, 2022-now

    University of California, Berkeley

  • BSc in Computer Science, 2018-2022

    Turing Class, School of EECS, Peking University

Recent Publications

Quickly discover relevant content by filtering publications.
(2024). Almost Optimal Time Lower Bound for Approximating Parameterized Clique, CSP, and More, under ETH.

arxiv eccc

(2023). Parameterized Inapproximability Hypothesis under ETH. Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024, (Best Paper Award).

arxiv eccc slides

(2023). Baby PIH: Parameterized Inapproximability of Min CSP. 39th Computational Complexity Conference (CCC), 2024.

arxiv eccc slides

(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

(2022). Constant Approximating Parameterized k-SetCover is W[2]-hard. Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.

arxiv slides