Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

• 全文链接
• 请求原文

作   者：

Bjorklund, Andreas;  Kaski, Petteri;  Williams, Ryan; 

作者机构：

Dept Elect Engn & Comp Sci;  Aalto Univ;  CSAIL;  MA 02139 USA;  Sweden;  Helsinki;  Lund Univ;  Finland;  77 Massachusetts Ave;  Lund;  MIT;  Cambridge;  Dept Comp Sci; 

关键词：

Finite field;  Finite vector space;  Hamiltonian cycle;  Permanent;  Besicovitch set;  Tabulation;  Fermionant;  Homogeneous polynomial;  Kakeya set;  Polynomial evaluation; 

期刊名称：

Algorithmica

i s s n：

0178-4617

年卷期：

2019 年 81 卷 10 期

页   码：

4010-4028

页   码：

摘   要：

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(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 multi-graph, 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 x m integer matrix with entries bounded in absolute value by a constant can be computed in time 2(m-Omega)(root m/log logm), improving an earlier algorithm of Bjorklund (in: Proceedings of the 15th SWAT, vol 17, pp 1-11, 2016) that runs in time 2(m-Omega)(root m/logm).