

Title: 
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants 
Author(s): 
Björklund, Andreas
;
Kaski, Petteri
;
Williams, Ryan

Date: 
20180101 
Language: 
en 
Department: 
Lund University Department of Computer Science Massachusetts Institute of Technology 
Series: 
Algorithmica 
ISSN: 
01784617 14320541 
DOInumber: 
10.1007/s0045301805137

Subject: 
Computer Science(all), Computer Science Applications, Applied Mathematics, 113 Computer and information sciences

Keywords: 
Besicovitch set, Fermionant, Finite field, Finite vector space, Hamiltonian cycle, Homogeneous polynomial, Kakeya set, Permanent, Polynomial evaluation, Tabulation, Computer Science(all), Computer Science Applications, Applied Mathematics, 113 Computer and information sciences

» Show full item record


Citation:
Björklund , A , Kaski , P & Williams , R 2018 , ' Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants ' Algorithmica . DOI: 10.1007/s0045301805137

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 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 degreeseparability 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 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 linearto 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).


Description:
 openaire: EC/H2020/338077/EU//TAPEASE

Permanent link to this item:
http://urn.fi/URN:NBN:fi:aalto201810165336
