Counting magic squares in quasi-polynomial time
| dc.creator | Barvinok, Alexander | |
| dc.creator | Samorodnitsky, Alex | |
| dc.creator | Yong, Alexander | |
| dc.date | 2007-03-08 | |
| dc.date.accessioned | 2026-07-07T07:50:53Z | |
| dc.date.available | 2026-07-07T07:50:53Z | |
| dc.description | We present a randomized algorithm, which, given positive integers n and t and a real number 0< epsilon <1, computes the number Sigma(n, t) of n x n non-negative integer matrices (magic squares) with the row and column sums equal to t within relative error epsilon. The computational complexity of the algorithm is polynomial in 1/epsilon and quasi-polynomial in N=nt, that is, of the order N^{log N}. A simplified version of the algorithm works in time polynomial in 1/epsilon and N and estimates Sigma(n,t) within a factor of N^{log N}. This simplified version has been implemented. We present results of the implementation, state some conjectures, and discuss possible generalizations. | |
| dc.description | 30 pages | |
| dc.identifier | https://arxiv.org/abs/math/0703227 | |
| dc.identifier | http://arxiv.org/abs/math/0703227 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/125317 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05A16, 68R05, 60C05 | |
| dc.title | Counting magic squares in quasi-polynomial time | |
| dc.type | text |