Showing cs.DSShow all
2 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 va…
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…