Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
(2018) In Algorithmica Abstract
We present two new data structures for computing values of an nvariate 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 q^{n} points using O(nqd^{2}) 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 degreeseparability condition and relies on (d/ s+ 1) ^{n}
^{+}
^{s} tabulated values... (More)We present two new data structures for computing values of an nvariate 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 q^{n} points using O(nqd^{2}) 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 degreeseparability condition and relies on (d/ s+ 1) ^{n}
^{+}
^{s} tabulated values to produce the value of P at any point using O(nq^{s}sq) arithmetic operations. Our data structures are based on generalizing upperbound 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 higherdegree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integervalued fermionants, a family of selfreducible 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
 20180918
 type
 Contribution to journal
 publication status
 epub
 subject
 keywords
 Besicovitch set, Fermionant, Finite field, Finite vector space, Hamiltonian cycle, Homogeneous polynomial, Kakeya set, Permanent, Polynomial evaluation, Tabulation
 in
 Algorithmica
 publisher
 Springer
 external identifiers

 scopus:85053686141
 ISSN
 01784617
 DOI
 10.1007/s0045301805137
 language
 English
 LU publication?
 yes
 id
 8435eb76a6734f54a8d044f60ba8e0cd
 date added to LUP
 20181026 08:10:16
 date last changed
 20190220 11:33:26
@article{8435eb76a6734f54a8d044f60ba8e0cd, abstract = {<p>We present two new data structures for computing values of an nvariate 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 degreeseparability 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 upperbound 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 higherdegree polynomial curves. As an application we show that the new data structures enable a faster algorithm for computing integervalued fermionants, a family of selfreducible 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 = {01784617}, keyword = {Besicovitch set,Fermionant,Finite field,Finite vector space,Hamiltonian cycle,Homogeneous polynomial,Kakeya set,Permanent,Polynomial evaluation,Tabulation}, language = {eng}, month = {09}, publisher = {Springer}, series = {Algorithmica}, title = {Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants}, url = {http://dx.doi.org/10.1007/s0045301805137}, year = {2018}, }