## 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(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^{s}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^{m-Ω(√m/log log m)}, improving an earlier algorithm of Björklund (2016) that runs in time 2^{m-Ω(√m/logm)}.

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

Title of host publication | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 |

Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Pages | 1-13 |

ISBN (Electronic) | 9783959770514 |

DOIs | |

Publication status | Published - 1 Feb 2018 |

MoE publication type | A4 Article in a conference publication |

Event | International Symposium on Parameterized and Exact Computation - Vienna, Austria Duration: 6 Sep 2017 → 8 Sep 2017 Conference number: 12 |

### Publication series

Name | Leibniz International Proceedings in Informatics |
---|---|

Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |

Volume | 89 |

ISSN (Electronic) | 1868-8969 |

### Conference

Conference | International Symposium on Parameterized and Exact Computation |
---|---|

Abbreviated title | IPEC |

Country | Austria |

City | Vienna |

Period | 06/09/2017 → 08/09/2017 |

## Keywords

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