21 citations · 61 across the 21 of their papers we have counts for
35 papers
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…
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
Near-optimal fitting of ellipsoids to random points
Aaron Potechin, Paxton Turner, Prayaag Venkat +1
Given independent standard Gaussian points in dimension , for what values of does there exist with high probability an origin-symmetric ellipsoid tha…
The Sixth Moment of Random Determinants
Dominik Beck, Zelin Lv, Aaron Potechin
In this paper, we determine the sixth moment of the determinant of an asymmetric random matrix where the entries are drawn independently from an arbitrary distribution…
On Mixing Distributions Via Random Orthogonal Matrices and the Spectrum of the Singular Values of Multi-Z Shaped Graph Matrices
Wenjun Cai, Aaron Potechin
In this paper, we introduce and analyze a new operation which mixes two distributions and via a random orthogonal matrix. In particular, we take …
Bounds on the Total Coefficient Size of Nullstellensatz Proofs of the Pigeonhole Principle and the Ordering Principle
Aaron Potechin, Aaron Zhang
In this paper, we investigate the total coefficient size of Nullstellensatz proofs. We show that Nullstellensatz proofs of the pigeonhole principle on pigeons require total coe…