Sökning: id:"swepub:oai:lup.lub.lu.se:8435eb76-a673-4f54-a8d0-44f60ba8e0cd" >
Generalized Kakeya ...
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
-
- Björklund, Andreas (författare)
- Lund University,Lunds universitet,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH
-
- Kaski, Petteri (författare)
- Aalto University
-
- Williams, Ryan (författare)
- Massachusetts Institute of Technology
-
(creator_code:org_t)
- 2018-09-18
- 2019
- Engelska 19 s.
-
Ingår i: Algorithmica. - : Springer Science and Business Media LLC. - 0178-4617 .- 1432-0541. ; 81:10, s. 4010-4028
- Relaterad länk:
-
http://dx.doi.org/10... (free)
-
visa fler...
-
https://link.springe...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
visa färre...
Abstract
Ämnesord
Stäng
- 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 (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 2m-Ω(m/loglogm), improving an earlier algorithm of Björklund (in: Proceedings of the 15th SWAT, vol 17, pp 1–11, 2016) that runs in time 2m-Ω(m/logm).
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- Besicovitch set
- Fermionant
- Finite field
- Finite vector space
- Hamiltonian cycle
- Homogeneous polynomial
- Kakeya set
- Permanent
- Polynomial evaluation
- Tabulation
Publikations- och innehållstyp
- art (ämneskategori)
- ref (ämneskategori)
Hitta via bibliotek
Till lärosätets databas