Fetching the paper…

Reading the bibliography…

A stability result using the matrix norm to bound the permanent · Around

2016

A stability result using the matrix norm to bound the permanent

Berkowitz, Ross, Devlin, Pat

Original
PDF
Post on X

Understand

We prove a stability version of a general result that bounds the permanent of a matrix in terms of its operator norm.

More specifically, suppose $A$ is an $n \times n$ matrix over $\mathbb{C}$ (resp.
$\mathbb{R}$), and let $\mathcal{P}$ denote the set of $n \times n$ matrices over $\mathbb{C}$ (resp.
$\mathbb{R}$) that can be written as a permutation matrix times a unitary diagonal matrix.

Built on

Étude des coefficients de Fourier des fonctions de L p ( G ) L^{p}(G)
Aline Bonami · 1970
Earlier work this paper cites.
The complexity of computing the permanent
Original
L. G. Valiant · 1979
Earlier work this paper cites.
Probability in Banach spaces
Michel Ledoux and Michel Talagrand · 1991
Earlier work this paper cites.
Projection constants of symmetric spaces and variants of Khintchine’s inequality
Hermann König, Carsten Schütt, and Nicole Tomczak-Jaegermann · 1999
Earlier work this paper cites.
On the complexity of mixed discriminants and related problems
Leonid Gurvits · 2005
Earlier work this paper cites.

Similar

Fast dimension reduction using Rademacher series on dual BCH codes
Nir Ailon and Edo Liberty · 2009
Cited alongside, same era.
The permanent of a square matrix
David G. Glynn · 2010
Cited alongside, same era.
Concentration and moment inequalities for polynomials of independent random variables
Warren Schudy and Maxim Sviridenko · 2012
Cited alongside, same era.
Generalizing and derandomizing Gurvits’s approximation algorithm for the permanent
Scott Aaronson and Travis Hance · 2014
Cited alongside, same era.

Then

Bounds on the permanent and some applications
Leonid Gurvits and Alex Samorodnitsky · 2014
Later among the works it cites.
Analysis of boolean functions
Ryan O’Donnell · 2014
Later among the works it cites.
Near invariance of the hypercube
Scott Aaronson and Hoi Nguyen · 2016
Closest in time.
On matrices of large permanent
Hoi Nguyen · 2016
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…