Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
| dc.contributor | Aalto-yliopisto | fi |
| dc.contributor | Aalto University | en |
| dc.contributor.author | Björklund, Andreas | en_US |
| dc.contributor.author | Kaski, Petteri | en_US |
| dc.contributor.author | Williams, Ryan | en_US |
| dc.contributor.department | Lund University | en_US |
| dc.contributor.department | Professorship Kaski Petteri | en_US |
| dc.contributor.department | Massachusetts Institute of Technology MIT | en_US |
| dc.contributor.department | Department of Computer Science | en |
| dc.date.accessioned | 2018-05-22T14:37:07Z | |
| dc.date.available | 2018-05-22T14:37:07Z | |
| dc.date.issued | 2018-02-01 | en_US |
| dc.description.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 (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). | en |
| dc.description.version | Peer reviewed | en |
| dc.format.extent | 1-13 | |
| dc.format.mimetype | application/pdf | en_US |
| dc.identifier.citation | Björklund , A , Kaski , P & Williams , R 2018 , Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants . in 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 . , 6 , Leibniz International Proceedings in Informatics , vol. 89 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-13 , International Symposium on Parameterized and Exact Computation , Vienna , Austria , 06/09/2017 . https://doi.org/10.4230/LIPIcs.IPEC.2017.6 | en |
| dc.identifier.doi | 10.4230/LIPIcs.IPEC.2017.6 | en_US |
| dc.identifier.isbn | 9783959770514 | |
| dc.identifier.issn | 1868-8969 | |
| dc.identifier.other | PURE UUID: 5be4855b-31d5-438a-a7ed-b11d3e8908af | en_US |
| dc.identifier.other | PURE ITEMURL: https://research.aalto.fi/en/publications/5be4855b-31d5-438a-a7ed-b11d3e8908af | en_US |
| dc.identifier.other | PURE LINK: http://www.scopus.com/inward/record.url?scp=85044722946&partnerID=8YFLogxK | en_US |
| dc.identifier.other | PURE FILEURL: https://research.aalto.fi/files/18927108/LIPIcs_IPEC_2017_6.pdf | en_US |
| dc.identifier.uri | https://aaltodoc.aalto.fi/handle/123456789/30929 | |
| dc.identifier.urn | URN:NBN:fi:aalto-201805222369 | |
| dc.language.iso | en | en |
| dc.publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH | |
| dc.relation.ispartof | International Symposium on Parameterized and Exact Computation | en |
| dc.relation.ispartofseries | 12th International Symposium on Parameterized and Exact Computation, IPEC 2017 | en |
| dc.relation.ispartofseries | Leibniz International Proceedings in Informatics | en |
| dc.relation.ispartofseries | Volume 89 | en |
| dc.rights | openAccess | en |
| dc.subject.keyword | Besicovitch set | en_US |
| dc.subject.keyword | Fermionant | en_US |
| dc.subject.keyword | Finite field | en_US |
| dc.subject.keyword | Finite vector space | en_US |
| dc.subject.keyword | Hamiltonian cycle | en_US |
| dc.subject.keyword | Homogeneous polynomial | en_US |
| dc.subject.keyword | Kakeya set | en_US |
| dc.subject.keyword | Permanent | en_US |
| dc.subject.keyword | Polynomial evaluation | en_US |
| dc.subject.keyword | Tabulation | en_US |
| dc.title | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants | en |
| dc.type | Conference article in proceedings | fi |
| dc.type.version | publishedVersion |
