Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
(2019) In Algorithmica 81(10). p.4010-4028- Abstract
We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q- 1 , our first data structure relies on (d+ 1) n
+
2 tabulated values of P to produce the value of P at any of the qn points using O(nqd2) arithmetic operations in the finite field. Assuming that s divides d and d / s divides q- 1 , our second data structure assumes that P satisfies a degree-separability condition and relies on (d/ s+ 1) n
+
s tabulated values... (More)We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q- 1 , our first data structure relies on (d+ 1) n
(Less)
+
2 tabulated values of P to produce the value of P at any of the qn points using O(nqd2) arithmetic operations in the finite field. Assuming that s divides d and d / s divides q- 1 , our second data structure assumes that P satisfies a degree-separability condition and relies on (d/ s+ 1) n
+
s tabulated values to produce the value of P at any point using O(nqssq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (Duke Math J 121(1):35–74, 2004), Saraf and Sudan (Anal PDE 1(3):375–379, 2008) and Dvir (Incidence theorems and their applications, 2012. arXiv:1208.5073) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (Partition functions of strongly correlated electron systems as fermionants, 2011. arXiv:1108.2461v1) that captures numerous fundamental algebraic and combinatorial functions such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m× m integer matrix with entries bounded in absolute value by a constant can be computed in time 2m-Ω(m/loglogm), improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time 2m-Ω(m/logm).
- author
- Björklund, Andreas LU ; Kaski, Petteri and Williams, Ryan
- organization
- publishing date
- 2019-10
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Besicovitch set, Fermionant, Finite field, Finite vector space, Hamiltonian cycle, Homogeneous polynomial, Kakeya set, Permanent, Polynomial evaluation, Tabulation
- in
- Algorithmica
- volume
- 81
- issue
- 10
- pages
- 19 pages
- publisher
- Springer
- external identifiers
-
- scopus:85053686141
- ISSN
- 0178-4617
- DOI
- 10.1007/s00453-018-0513-7
- language
- English
- LU publication?
- yes
- id
- 8435eb76-a673-4f54-a8d0-44f60ba8e0cd
- date added to LUP
- 2018-10-26 08:10:16
- date last changed
- 2022-04-25 18:20:19
@article{8435eb76-a673-4f54-a8d0-44f60ba8e0cd,
abstract = {{<p>We present two new data structures for computing values of an n-variate polynomial P of degree at most d over a finite field of q elements. Assuming that d divides q- 1 , our first data structure relies on (d+ 1) <sup>n</sup><br>
<sup>+</sup><br>
<sup>2</sup> tabulated values of P to produce the value of P at any of the q<sup>n</sup> points using O(nqd<sup>2</sup>) arithmetic operations in the finite field. Assuming that s divides d and d / s divides q- 1 , our second data structure assumes that P satisfies a degree-separability condition and relies on (d/ s+ 1) <sup>n</sup><br>
<sup>+</sup><br>
<sup>s</sup> tabulated values to produce the value of P at any point using O(nq<sup>s</sup>sq) arithmetic operations. Our data structures are based on generalizing upper-bound constructions due to Mockenhaupt and Tao (Duke Math J 121(1):35–74, 2004), Saraf and Sudan (Anal PDE 1(3):375–379, 2008) and Dvir (Incidence theorems and their applications, 2012. arXiv:1208.5073) for Kakeya sets in finite vector spaces from linear to higher-degree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integer-valued fermionants, a family of self-reducible polynomial functions introduced by Chandrasekharan and Wiese (Partition functions of strongly correlated electron systems as fermionants, 2011. arXiv:1108.2461v1) that captures numerous fundamental algebraic and combinatorial functions such as the determinant, the permanent, the number of Hamiltonian cycles in a directed multigraph, as well as certain partition functions of strongly correlated electron systems in statistical physics. In particular, a corollary of our main theorem for fermionants is that the permanent of an m× m integer matrix with entries bounded in absolute value by a constant can be computed in time 2m-Ω(m/loglogm), improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time 2m-Ω(m/logm).</p>}},
author = {{Björklund, Andreas and Kaski, Petteri and Williams, Ryan}},
issn = {{0178-4617}},
keywords = {{Besicovitch set; Fermionant; Finite field; Finite vector space; Hamiltonian cycle; Homogeneous polynomial; Kakeya set; Permanent; Polynomial evaluation; Tabulation}},
language = {{eng}},
number = {{10}},
pages = {{4010--4028}},
publisher = {{Springer}},
series = {{Algorithmica}},
title = {{Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants}},
url = {{http://dx.doi.org/10.1007/s00453-018-0513-7}},
doi = {{10.1007/s00453-018-0513-7}},
volume = {{81}},
year = {{2019}},
}