5 citations · 5 across the 5 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Smooth Trade-off for Tensor PCA via Sharp Bounds for Kikuchi Matrices
Pravesh K. Kothari, Jeff Xu
In this work, we revisit algorithms for Tensor PCA: given an order- tensor of the form where is a random symmetric Gaussian tensor with unit var…
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 , and large enough constant , with high probability over the choice of , the \Erdos-\Renyi random graph distribution, t…
cs.DS2021
Certifying solution geometry in random CSPs: counts, clusters and balance
Jun-Ting Hsieh, Sidhanth Mohanty, Jeff Xu
An active topic in the study of random constraint satisfaction problems (CSPs) is the geometry of the space of satisfying or almost satisfying assignments as the function of the de…