5 citations · 6 across the 8 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
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 such that there is an ellipsoid in th…
cs.CC2023★ 1 cited
Is Planted Coloring Easier than Planted Clique?
Pravesh K. Kothari, Santosh S. Vempala, Alexander S. Wein +1
We study the computational complexity of two related problems: recovering a planted -coloring in , and finding efficiently verifiable witnesses of non--colorability…