Xifan Yu

About me

I am a 6th 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, including graph theory, average-case complexity, spectral methods, Sum-of-Squares algorithms, and high-dimensional statistics. Recently I have become interested in finite free probability, numerical linear algebra, and the theory of language generation.

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

• Inequalities for rank-two permanents and finite free convolutions
  Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu. Manuscript, 2026.

• Analysis of polynomial threshold functions on random regular graphs: computational complexity of detecting noisy random lifts
  Xifan Yu. In Submission, 2026.

• Strong refutation of random ordering CSPs
  Xifan Yu. In Submission, 2026.

• Large growth happens: Gaussian elimination with partial pivoting on random matrices
  Daniel A. Spielman, Xifan Yu. In Submission, 2026.

• Stable algorithms lower bounds for estimation from MMSE discontinuities (Extended Abstract)
  Xifan Yu, Ilias Zadik. Conference on Learning Theory (COLT), 2026.

• Differentially private language generation in the limit (Extended Abstract)
  Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou. Conference on Learning Theory (COLT), 2026.

• Language Generation with Infinite Contamination
  Anay Mehrotra, Grigoris Velegkas, Xifan Yu, Felix Zhou. Conference on Learning Theory (COLT), 2026.

• 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. 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