Xifan Yu

About me

I am a 5th year PhD student in computer science at Yale University and I am fortunate to be advised by Dan Spielman. Before then, I was an undergraduate at the University of Chicago, advised by Lorenzo Orecchia.

I am broadly interested in theoretical computer science. Recently I am interested in graph theory, average-case complexity, Sum-of-Squares algorithms, and high-dimensional statistics.

Previously, I participated in competitive programming. I am a GO player, and I was a member of UChicago GO Team.

Here is my CV.

Publications and Preprints

• Language Generation with Infinite Contamination
  Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou. In Submission, 2025.

• Counting stars is constant-degree optimal for detecting any planted subgraph
  Xifan Yu, Ilias Zadik, Peiyuan Zhang. Mathematical Statistics and Learning, 2025+.

• Statistical inference of a ranked community in a directed graph
  Dmitriy Kunisky, Daniel A. Spielman, Alexander S. Wein, Xifan Yu. To appear in Symposium on Theory of Computing (STOC), 2025.

• Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
  Dmitriy Kunisky, Xifan Yu. Symposium on Foundations of Computer Science (FOCS), 2024.

• Counting stars is constant-degree optimal for detecting any planted subgraph, Extended Abstract
  Xifan Yu, Ilias Zadik, Peiyuan Zhang. Conference on Learning Theory (COLT), 2024.

• A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
  Dmitriy Kunisky, Xifan Yu. Computational Complexity Conference (CCC), 2023.

Master Thesis

• Anomaly detection on connected subgraphs via constant-factor approximation algorithms for the Elevated Mean problem
  Xifan Yu, Advisor: Lorenzo Orecchia

Miscellaneous Writings

• A survey of the Neggers-Stanley conjecture
  Xifan Yu, 2020 UChicago Math REU paper, Mentor: Adan Medrano Martin del Campo