Projects per year

### 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 (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 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√).

Original language | English |
---|---|

Pages (from-to) | 4010-4028 |

Journal | Algorithmica |

Volume | 81 |

Issue number | 10 |

DOIs | |

Publication status | Published - 1 Oct 2019 |

MoE publication type | A1 Journal article-refereed |

### Keywords

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

## Fingerprint Dive into the research topics of 'Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants'. Together they form a unique fingerprint.

## Projects

- 1 Finished

## TAPEASE: Theory and Practice of Advance Search and Enumeration

01/01/2014 → 31/12/2019

Project: EU: ERC grants

## Cite this

Björklund, A., Kaski, P., & Williams, R. (2019). Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants.

*Algorithmica*,*81*(10), 4010-4028. https://doi.org/10.1007/s00453-018-0513-7