3 papers
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
Sum-of-Squares Lower Bounds for Densest -Subgraph
Chris Jones, Aaron Potechin, Goutham Rajendran +1
Given a graph and an integer , Densest -Subgraph is the algorithmic task of finding the subgraph on vertices with the maximum number of edges. This is a fundamental probl…
math.CO2014
A note on a problem of Erdos and Rothschild
Aaron Potechin
A set of triangles sharing a common edge is a called a book of size . Letting denote the size of the largest book in a graph , Erdős and Rothschild \cite{erdostwo…