{"id":"arxiv/2604.01367","url":"https://arxiv.org/abs/2604.01367","tags":["cs.DS","math-ph","math.PR","quant-ph"],"score":0,"title":"Approximating the Permanent of a Random Matrix with Polynomially Small Mean: Zeros and Universality","domain":"cs.DS","source":"arxiv","authors":["Frederic Koehler","Pui Kuen Leung"],"reviews":0,"subject":"cs.DS","summary":"We study algorithms for approximating the permanent of a random matrix when the entries are slightly biased away from zero. This question is motivated by the goal of understanding the classical complexity of linear optics and \\emph{boson sampling} (Aaronson and Arkhipov '11; Eldar and Mehraban '17). Barvinok's interpolation method enables efficient approximation of the permanent, provided one can establish a sufficiently large zero-free region for the polynomial $\\mathrm{per}(zJ + W)$, where $J$ is the all-ones matrix and $W$ is a random matrix with independent mean-zero entries. We show…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}