On the permanent of random tensors
2025
Read On the permanent of random tensors (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-07000.txt.
Introduction
Malihe Nobakht Kooshkghazi and Hamidreza Afshin tackle the permanent of random tensors, a sum over products that grows brutally with size. For plain matrices the permanent is already famously hard to compute exactly. For tensors, the multi-way arrays used across modern data work, it is harder still. Yet permanents carry meaning in fields from physics to counting problems.
The authors design methods that estimate the permanent instead of computing it exactly. One runs in near-polynomial time with firm guarantees, for tensors whose entries average out above a set floor. A second scheme trades a little accuracy for speed in a controlled way. Both target random complex tensors rather than worst-case ones. The work gives approximation a foothold in a problem long treated as out of reach.
Catalog record
| YEAR | 2025 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-07000
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the permanent of random tensors Thanks: ∗ Corresponding author Abstract . The exact computation of permanent for high-dimensional tensors is a hard problem. Having in mind the applications of permanents in other fields, providing an algorithm for the approximation of tensor permanents is an attractive subject. In this paper, we design a deterministic quasi-polynomial time algorithm and a PTAS that computes the permanent of complex random tensors that its module of the mean is at least 1 p o l y l o g ( n ) \frac{1}{polylog(n)} . Keywords : Algorithm, Distribution, Matrix, Permanent, Tensor. 2010 AMS Subject Classification : 15A15, 15A69, 68W25. Malihe Nobakht-Kooshkghazi ∗,§ , Hamidreza Afshin § § Department of Mathematics, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran e-mails: [email protected],[email protected] 1. Introduction A tensor A=(a_{i_{1}\dots i_{d}})_{n_{1}\times\dots\times n_{d}} is a multi-array of entries a_{i_{1}\dots i_{d}}\in\mathbb{F} , where i_{j}=1,\dots,n_{j} for j=1,\dots,d and \mathbb{F} is a field. In this paper, we consider complex tensors, that is, those tensors for which \mathbb{F}=\mathbb{C} . Here, d and (n_{1},\dots,n_{d}) are referred to as the order and the dimension of A , respectively. When n_{1}=n_{2}=\cdots=n_{d}=n , we say that A is a tensor of order d and dimension n . In this paper, we only consider tensors of order d and dimension n . We refer the interested reader to [ 13 ] for more information on the theory of tensors. The permanent of a matrix was introduced by Cauchy [ 8 ] in 1812. We know that the problem of computing the permanent of a non-negative matrix, or even that of a (0,1) -matrix, lies in the class of \# P-hard problems [ 17 ] . Ryser presented an algorithm for computing the permanent of an n\times n matrix that runs in n2^{n} time [ 15 ] . In 2017, Alexander Barvinok presented a quasi-polynomial deterministic algorithm to approximate the permanent of an n\times n matrix A=(a_{ij}) with \delta\leq a_{ij}\leq 1 , for all i,j , in n^{\mathcal{O}(\ln n-\ln\varepsilon)} time [ 2 ] . In physics, the permanent of a matrix appears as the amplitudes of bosonic systems. Motivated by these connections, in 2011, Aaronson and Arkhipov introduced a model of quantum computation known as Boson Sampling [ 1 ] . Even though boson sampling is a highly rudimentary quantum computational device, Aaronson and Arkhipov showed that assuming plausible conjectures about hardness of approximation and anti-concentration of the permanent of i.i.d. Gaussian matrices, approximately sampling from the Boson Sampling device is hard for a classical computer unless notable conjectures in computer science (namely non-collapse of the polynomial hierarchy) do not hold. To be more specific, one of the conjectures known as the hardness of approximating the permanent states that it is \# P-hard to approximate the permanent of matrix with i.i.d. complex Gaussian entries to within inverse-polynomial multiplicative error. In [ 11 ] , Eldar and Mehraban showed that if we sample matrices from complex Gaussian entries with nonzero (inverse polyloglog) but vanishing mean, then there is a quasi-polynomial time algorithm to approximate the permanent within multiplicative error. The technique Eldar and Mehraban used is based on a recent approach by Alexander Barvinok that considers a low-degree polynomial ”additive” approximation to the logarithm of the permanent polynomial (this gives a multiplicative approximation to the permanent) [ 4 ] . In particular, Eldar and Mehraban considered the single variable polynomial g(z)=per(J+Az) , where J is the all-ones matrix. They show that the disk of radius L in the complex plan has at most \mathcal{O}(L^{2}) zeros of g , and hence, there is a curve that connects z=0 to z=L that avoids all the roots with a significant margin. They then use analytic continuation for \log g(z) along this curve and showed that low-order Taylor polynomial expansion along this curve converges. In 2021, Zhengfeng Ji, Zhihan Jin and Pinyan Lu subsequently improved this result by improving the value of the mean to inverse polylogarithmic [ 12 ] . They furthermore simplified the description of the algorithm. Ji et al. used nontrivial probabilistic tools to showed that if we simply Taylor expand g(z) in powers of z , then the first few ( \log n ) terms of the expansion would constitute a good multiplicative approximation. The permanent of a tensor was introduced by Cayley [ 9 ] in 1849. In [ 10 ] , the permanent of tensor A of order d and dimension n_{1}\times\dots\times n_{d} is defined by per(A):=\sum\limits_{\sigma_{k}}\prod_{i=1}^{n_{1}}a_{i\sigma_{2}(i)\dots\sigma_{d}(i)}, where the summation runs over all one-to-one functions \sigma_{k} from \{1,\dots,n_{1}\} to \{1,\dots,n_{k}\} and k=2,\dots,d , with per(A)=0 if n_{1}>n_{k} for some k . In recent years, some properties and applications of the permanents of tensors have been studied by Dow and Gibson [ 10 ] , and also by Wang and Zhang [ 18 ] . The use of permanents of tensors facilitates the solutions of many problems in other branches of mathematics and other sciences. For example, transversals in Latin hypercubes, 1 -factors of hypergraphs, MDS codes, combinatorial designs, the number of Steiner systems, and the description of the interactions of elementary particles in physics [ 16 ] all depend on the permanents of tensors. Since the computation of the permanent of non-negative matrices is \#P -complete and tensors are a generalization of matrices to higher dimensions, computing the permanent of non-negative tensors is harder than matrices. Because of this hardness in the worst case, research has also focused on computing an approximation for the value of permanent. Similar to the matrix case, the computational complexity of computing the permanent of a tensor is important to complexity theory and has been studied. In [ 5 ] , an algorithm is presented for computing the permanent of tensors whose entries of it are in the special form. In 2019, Alexander Barvinok presented a quasi-polynomial time algorithm to approximate the permanent of an n\times n complex matrix, where the absolute value of each diagonal entry is at least \lambda times bigger than the sum of the absolute values of all other entries in the same row, for any \lambda>1 . Also, they generalized this result to the permanent of tensors [ 4 ] . Their method presented an algorithm that computes an additive approximation of \ln(per(A)) and then exponentiates the result. The approach in [ 12 ] stated here for the permanent of a random tensor that module of its mean value is at least \frac{1}{polylog(n)} ( |\mu|>\frac{1}{polylog(n)} ), where d\geq 3 and d\in\mathcal{O}(polylog(n)) . Here instead of trying to compute per(X) directly, we write \frac{per(X)}{(n!)^{d-1}} as \sum\limits_{k=0}^{t}a_{k}z^{k} , where z=\frac{1}{\mu} and t=\ln n+\ln\frac{1}{\varepsilon} and \varepsilon is the approximation parameter, then we give a simple approximation for this summation. Also, we show that this approximation is a good approximation by taking a detour by artificially defining several related quantities and using the moment bounds and recursions among them to inductively show the desired approximation rate. Also, our algorithm has time complexity n^{\mathcal{O}(d\ln\frac{n}{\varepsilon})} . The proof strategies here are similar to those in the matrix case. The remainder of this paper is organized as follows. In Section 2 , we study the relation between the permanents of some tensors and finite series. In section 3 , we give