Jeff Xu

jeffxusichao AT cmu DOT edu

I am a fifth year PhD student in the Theory Group at CMU, advised by Pravesh Kothari. Recently, 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:

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

with Aaron Potechin.
In submission.

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

In submission.

Sum-of-Squares Lower Bounds for Independent Set on 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 Bounds: Degree-2 to Degree-4. arxiv

with Sidhanth Mohanty, and Prasad Raghavendra.
STOC 2020.

Teaching Experience:

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

Teaching Assistant

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

Head Teaching Assistant


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