Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
(2018) 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 89. 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 q1, 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(nqd^{2}) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q1, 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 (2004),... (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 q1, 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(nqd^{2}) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q1, 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 (2004), Saraf and Sudan (2008), and Dvir (2009) 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 (2011) that captures numerous fundamental algebraic and combinatorial invariants 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 2^{mΩ(√m/log log m)}, improving an earlier algorithm of Björklund (2016) that runs in time 2^{mΩ(√m/logm)}.
(Less)
 author
 Björklund, Andreas ^{LU} ; Kaski, Petteri and Williams, Ryan
 organization
 publishing date
 20180201
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 Besicovitch set, Fermionant, Finite field, Finite vector space, Hamiltonian cycle, Homogeneous polynomial, Kakeya set, Permanent, Polynomial evaluation, Tabulation
 host publication
 12th International Symposium on Parameterized and Exact Computation, IPEC 2017
 volume
 89
 publisher
 Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing
 conference name
 12th International Symposium on Parameterized and Exact Computation, IPEC 2017
 conference location
 Vienna, Austria
 conference dates
 20170906  20170908
 external identifiers

 scopus:85044722946
 ISBN
 9783959770514
 DOI
 10.4230/LIPIcs.IPEC.2017.6
 language
 English
 LU publication?
 yes
 id
 2e3ad8cfadca46449bf9bccac635fc83
 date added to LUP
 20180411 14:32:48
 date last changed
 20190106 13:50:59
@inproceedings{2e3ad8cfadca46449bf9bccac635fc83, 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 q1, our first data structure relies on (d+1)<sup>n+2</sup> tabulated values of P to produce the value of P at any of the qn points using O(nqd<sup>2</sup>) arithmetic operations in the finite field. Assuming that s divides d and d/s divides q1, our second data structure assumes that P satisfies a degreeseparability condition and relies on (d/s + 1)<sup>n+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 (2004), Saraf and Sudan (2008), and Dvir (2009) 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 (2011) that captures numerous fundamental algebraic and combinatorial invariants 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 2<sup>mΩ(√m/log log m)</sup>, improving an earlier algorithm of Björklund (2016) that runs in time 2<sup>mΩ(√m/logm)</sup>.</p>}, author = {Björklund, Andreas and Kaski, Petteri and Williams, Ryan}, isbn = {9783959770514}, keyword = {Besicovitch set,Fermionant,Finite field,Finite vector space,Hamiltonian cycle,Homogeneous polynomial,Kakeya set,Permanent,Polynomial evaluation,Tabulation}, language = {eng}, location = {Vienna, Austria}, month = {02}, publisher = {Schloss Dagstuhl LeibnizZentrum fur Informatik GmbH, Dagstuhl Publishing}, title = {Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants}, url = {http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.6}, volume = {89}, year = {2018}, }