Jeff Xu

collaborators

2 papers

cs.DS2024

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

Pravesh Kothari, Aaron Potechin, Jeff Xu

We prove that for every $D \in N$ , and large enough constant $d \in N$ , with high probability over the choice of $G \sim G (n, d / n)$ , the \Erdos-\Renyi random graph distribution, t…

math.PR2023

Ellipsoid Fitting Up to a Constant

Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin +1

In [Sau11,SPW13], Saunderson, Parrilo and Willsky asked the following elegant geometric question: what is the largest $m = m (d)$ such that there is an ellipsoid in $R^{d}$ th…