From the 1 of 6 linked papers with an AI index.
6 papers
The Sixth Moment of Random Determinants for Arbitrarily Distributed Random Entries
Dominik Beck, Zelin Lv, Aaron Potechin
The paper derives a closed‑form expression for the sixth moment of the determinant of an n×n matrix with i.i.d. entries of any distribution, using a combinatorial decomposition of…
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and designated terminals. The goal is to partition the vertices of the grap…
On induced subgraphs of with maximum degree
Aaron Potechin, Hing Yin Tsang
In this paper, we consider induced subgraphs of the Hamming graph . We show that if and induces a subgraph of with maximum degree…
Analysing the Moments of the Determinant of a Random Matrix Via Analytic Combinatorics of Permutation Tables
Dominik Beck, Zelin Lv, Aaron Potechin
We consider the following natural question. Given a matrix with i.i.d. random entries, what are the moments of the determinant of ? In other words, what is $\mathbb{E}[\det(…
Sum-of-squares lower bounds for Non-Gaussian Component Analysis
Ilias Diakonikolas, Sushrut Karmalkar, Shuo Pang +1
Non-Gaussian Component Analysis (NGCA) is the statistical task of finding a non-Gaussian direction in a high-dimensional dataset. Specifically, given i.i.d.\ samples from a distrib…
On the second moment of the determinant of random symmetric, Wigner, and Hermitian matrices
Dominik Beck, Zelin Lv, Aaron Potechin
In this paper, we analyze the second moment of the determinant of random symmetric, Wigner, and Hermitian matrices. Using analytic combinatorics techniques, we determine the second…