Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
© 2018 Andreas Björklund, Petteri Kaski, and Ryan Williams. 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 pr...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137359 |
| _version_ | 1826207748098883584 |
|---|---|
| author | Williams, Richard Ryan Björklund, Andreas Kaski, Petteri |
| 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 Williams, Richard Ryan Björklund, Andreas Kaski, Petteri |
| author_sort | Williams, Richard Ryan |
| collection | MIT |
| description | © 2018 Andreas Björklund, Petteri Kaski, and Ryan Williams. 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). |
| first_indexed | 2024-09-23T13:54:41Z |
| format | Article |
| id | mit-1721.1/137359 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:54:41Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1373592023-02-03T20:26:33Z Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants Williams, Richard Ryan Björklund, Andreas Kaski, Petteri Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2018 Andreas Björklund, Petteri Kaski, and Ryan Williams. 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). 2021-11-04T16:28:43Z 2021-11-04T16:28:43Z 2018 2021-03-30T14:57:25Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137359 Williams, Richard Ryan, Björklund, Andreas and Kaski, Petteri. 2018. "Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants." Leibniz International Proceedings in Informatics, LIPIcs, 89. en 10.4230/LIPIcs.IPEC.2017.6 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Richard Ryan Björklund, Andreas Kaski, Petteri 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 | https://hdl.handle.net/1721.1/137359 |
| work_keys_str_mv | AT williamsrichardryan generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants AT bjorklundandreas generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants AT kaskipetteri generalizedkakeyasetsforpolynomialevaluationandfastercomputationoffermionants |