License
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://drops.dagstuhl.de/opus/volltexte/2018/8572/
Go to the corresponding LIPIcs Volume Portal


Björklund, Andreas ; Kaski, Petteri ; Williams, Ryan

Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants

pdf-format:
LIPIcs-IPEC-2017-6.pdf (0.5 MB)


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
Seminar: 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)
Issue Date: 2018
Date of publication: 23.02.2018


DROPS-Home | Imprint | Privacy Published by LZI