Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

Andreas Björklund, Petteri Kaski, Ryan Williams

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

1 Sitaatiot (Scopus)
86 Lataukset (Pure)


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

Otsikko12th International Symposium on Parameterized and Exact Computation, IPEC 2017
KustantajaSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (elektroninen)9783959770514
DOI - pysyväislinkit
TilaJulkaistu - 1 helmikuuta 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Symposium on Parameterized and Exact Computation - Vienna, Itävalta
Kesto: 6 syyskuuta 20178 syyskuuta 2017
Konferenssinumero: 12


NimiLeibniz International Proceedings in Informatics
KustantajaSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
ISSN (elektroninen)1868-8969


ConferenceInternational Symposium on Parameterized and Exact Computation

Sormenjälki Sukella tutkimusaiheisiin 'Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä