Advanced

Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

Björklund, Andreas LU ; Kaski, Petteri and Williams, Ryan (2018) In Algorithmica
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
+
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).

(Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
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
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
2019-02-20 11:33:26
@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},
  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/s00453-018-0513-7},
  year         = {2018},
}