Jeff Xu

jeffxusichao AT ttic DOT edu

Hi! I am currently a Postdoc/Research Assistant Professor at TTIC.

Previously, I was a PhD student in the Theory Group at CMU, advised by Pravesh Kothari. Throughout my grad school, I have spent most of my time thinking about convex relaxation hierarchies and their limitations, as well as the intersection of TCS and random matrix theory.

Prior to CMU, I obtained my B.A. in Mathematics at UC Berkeley, where I had the fortune of working with Prasad Raghavendra. I am also grateful for the mentorship of Siu On Chan at CUHK.

Papers:

Sharp Phase Transition for Ellipsoid Fitting arxiv.

with Sofia de la Cerda, Aaron Potechin, and Madhur Tulsiani.

Strongly Refuting Random CSP without Literals arxiv.

with Siu On Chan and Tommaso d’Orsi.
FOCS 2026.

Sharp Bound on the Lovász Theta Function for Random Graphs

with Aaron Potechin.
FOCS 2026.

Smooth Tradeoff for Tensor PCA via Sharp Bounds for Kikuchi Matrices arxiv.

with Pravesh K. Kothari.
SODA 2026.

Sum-of-Squares Lower Bounds for Coloring Random Graphs.

with Aaron Potechin.
STOC 2025.

Switching Graph Matrix Norm Bounds: from i.i.d. to Random Regular Graphs arxiv.

CCC 2025. (Best Student Paper)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs. arxiv

with Pravesh Kothari, and Aaron Potechin.
STOC 2024.

Ellipsoid Fitting Up to a Constant. arxiv

with Jun-Ting Hsieh, Pravesh Kothari, and Aaron Potechin.
ICALP 2023.

Is Planted Coloring Easier than Planted Clique? arxiv

with Pravesh Kothari, Santosh S. Vempala, and Alex Wein.
COLT 2023.

Sum-of-Squares Lower Bounds for Densest k-Subgraph. arxiv

with Chris Jones, Aaron Potechin, and Goutham Rajendran.
STOC 2023.

Polynomial-Time Power-Sum Decomposition of Polynomials. arxiv

with Mitali Bafna, Jun-Ting Hsieh, and Pravesh Kothari.
FOCS 2022.

Certifying solution geometry in random CSPs: counts, clusters and balance. arxiv

with Jun-Ting Hsieh, and Sidhanth Mohanty.
CCC 2022.

Sum-of-Squares Lower Bounds for Sparse Independent Set. arxiv

with Chris Jones, Aaron Potechin, Goutham Rajendran, and Madhur Tulsiani.
FOCS 2021.

Lifting Sum-of-Squares Lower Bound: Degree-2 to Degree-4. arxiv

with Sidhanth Mohanty, and Prasad Raghavendra.
STOC 2020.

Teaching Experience:

CMU 15-455: Undegraduate Complexity Theory. (Spring 2021).

Teaching Assistant

CMU 15-859: Randomness in Computation. (Fall 2022).

Teaching Assistant

UC Berkeley CS170: Efficient Algorithms and Intractable Problems. (Fall 2018, Spring 2020).

Teaching Assistant

UC Berkeley CS 174: Randomized Algorithms. (Spring, Fall 2019).

Head Teaching Assistant

Misc:
I hope one day freedom and liberty will root in my country.