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 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 (2004),... (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 (2004), Saraf and Sudan (2008), and Dvir (2009) 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 (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 2m-Ω(√m/log log m), improving an earlier algorithm of Björklund (2016) that runs in time 2m-Ω(√m/logm).
(Less)
- author
- Björklund, Andreas LU ; Kaski, Petteri and Williams, Ryan
- organization
- publishing date
- 2018-02-01
- 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 - Leibniz-Zentrum für Informatik
- conference name
- 12th International Symposium on Parameterized and Exact Computation, IPEC 2017
- conference location
- Vienna, Austria
- conference dates
- 2017-09-06 - 2017-09-08
- external identifiers
-
- scopus:85044722946
- ISBN
- 9783959770514
- DOI
- 10.4230/LIPIcs.IPEC.2017.6
- language
- English
- LU publication?
- yes
- id
- 2e3ad8cf-adca-4644-9bf9-bccac635fc83
- date added to LUP
- 2018-04-11 14:32:48
- date last changed
- 2022-03-25 01:16:31
@inproceedings{2e3ad8cf-adca-4644-9bf9-bccac635fc83,
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+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 q-1, our second data structure assumes that P satisfies a degree-separability 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 upper-bound constructions due to Mockenhaupt and Tao (2004), Saraf and Sudan (2008), and Dvir (2009) 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 (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}},
booktitle = {{12th International Symposium on Parameterized and Exact Computation, IPEC 2017}},
isbn = {{9783959770514}},
keywords = {{Besicovitch set; Fermionant; Finite field; Finite vector space; Hamiltonian cycle; Homogeneous polynomial; Kakeya set; Permanent; Polynomial evaluation; Tabulation}},
language = {{eng}},
month = {{02}},
publisher = {{Schloss Dagstuhl - Leibniz-Zentrum für Informatik}},
title = {{Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants}},
url = {{http://dx.doi.org/10.4230/LIPIcs.IPEC.2017.6}},
doi = {{10.4230/LIPIcs.IPEC.2017.6}},
volume = {{89}},
year = {{2018}},
}