Xuandi Ren
Ph.D Candidate in Computer Science
University of California, Berkeley
Biography
I am a third-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.
(2023).
Parameterized Inapproximability Hypothesis under ETH.
Proceedings of the 56th Annual ACM Symposium on Theory of Computing (STOC), 2024, (Best Paper Award).
(2023).
Baby PIH: Parameterized Inapproximability of Min CSP.
39th Computational Complexity Conference (CCC), 2024.
(2023).
Improved Hardness of Approximating k-Clique under ETH.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2023.
(2022).
Constant Approximating Parameterized k-SetCover is W[2]-hard.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023.