Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
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)[superscript n+2] tabulated values of P to produce the value of P at any of the q[super...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2018
|
| Online Access: | http://hdl.handle.net/1721.1/118295 https://orcid.org/0000-0003-2326-2233 |
| _version_ | 1811086699441160192 |
|---|---|
| author | Björklund, Andreas Kaski, Petteri Williams, Richard Ryan |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Björklund, Andreas Kaski, Petteri Williams, Richard Ryan |
| author_sort | Björklund, Andreas |
| collection | MIT |
| description | 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)[superscript n+2] tabulated values of P to produce the value of P at any of the q[superscript n] points using O(nqd[superscript 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)[superscript n+s] tabulated values to produce the value of P at any point using O(nq[superscript s]sq) 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 2[superscript m−(√m/ log log m)], improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time 2[superscript m−(√m/ log m)]. |
| first_indexed | 2024-09-23T13:31:02Z |
| format | Article |
| id | mit-1721.1/118295 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:31:02Z |
| publishDate | 2018 |
| publisher | Springer US |
| record_format | dspace |
| spelling | mit-1721.1/1182952022-10-01T15:38:16Z Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants Björklund, Andreas Kaski, Petteri Williams, Richard Ryan Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Williams, Richard Ryan 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)[superscript n+2] tabulated values of P to produce the value of P at any of the q[superscript n] points using O(nqd[superscript 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)[superscript n+s] tabulated values to produce the value of P at any point using O(nq[superscript s]sq) 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 2[superscript m−(√m/ log log m)], improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time 2[superscript m−(√m/ log m)]. National Science Foundation (U.S.) (Grant CCF-1741638) National Science Foundation (U.S.) (Grant CCF-1741615) 2018-10-01T13:56:55Z 2018-10-01T13:56:55Z 2018-09 2017-12 2018-09-19T03:55:13Z Article http://purl.org/eprint/type/JournalArticle 0178-4617 1432-0541 http://hdl.handle.net/1721.1/118295 Björklund, Andreas, et al. “Generalized Kakeya Sets for Polynomial Evaluation and Faster Computation of Fermionants.” Algorithmica, Sept. 2018. © 2018 The Authors https://orcid.org/0000-0003-2326-2233 en https://doi.org/10.1007/s00453-018-0513-7 Algorithmica Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ The Author(s) application/pdf Springer US Springer US |
| spellingShingle | Björklund, Andreas Kaski, Petteri Williams, Richard Ryan Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title_full | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title_fullStr | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title_full_unstemmed | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title_short | Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants |
| title_sort | generalized kakeya sets for polynomial evaluation and faster computation of fermionants |
| url | http://hdl.handle.net/1721.1/118295 https://orcid.org/0000-0003-2326-2233 |
| work_keys_str_mv | AT bjorklundandreas generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants AT kaskipetteri generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants AT williamsrichardryan generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants |