License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2017.6
URN: urn:nbn:de:0030-drops-85728
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8572/
Björklund, Andreas ;
Kaski, Petteri ;
Williams, Ryan
Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants
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 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 degree-separability condition and relies on (d/s+1)^{n+s} tabulated values to produce the value of P at any point using O(nq^ssq) 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-by-m integer matrix with entries bounded in absolute value by a constant can be computed in time 2^{m-Omega(sqrt(m/log log m))}, improving an earlier algorithm of Bjorklund (2016) that runs in time 2^{m-Omega(sqrt(m/log m))}.
BibTeX - Entry
@InProceedings{bjrklund_et_al:LIPIcs:2018:8572,
author = {Andreas Bj{\"o}rklund and Petteri Kaski and Ryan Williams},
title = {{Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants}},
booktitle = {12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
pages = {6:1--6:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-051-4},
ISSN = {1868-8969},
year = {2018},
volume = {89},
editor = {Daniel Lokshtanov and Naomi Nishimura},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8572},
URN = {urn:nbn:de:0030-drops-85728},
doi = {10.4230/LIPIcs.IPEC.2017.6},
annote = {Keywords: Besicovitch set, fermionant, finite field, finite vector space, Hamiltonian cycle, homogeneous polynomial, Kakeya set, permanent, polynomial evaluatio}
}
|
Keywords: |
|
Besicovitch set, fermionant, finite field, finite vector space, Hamiltonian cycle, homogeneous polynomial, Kakeya set, permanent, polynomial evaluatio |
|
Collection: |
|
12th International Symposium on Parameterized and Exact Computation (IPEC 2017) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
02.03.2018 |
