Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

DOI10.4230/LIPICS.IPEC.2017.6MaRDI QIDQ5111865zbMATH OpenFDO

Authors Andreas Björklund, Petteri Kaski, Ryan Williams

Publication date 27 May 2020

zbMATH Keywords

Hamiltonian cyclefinite fieldpermanenthomogeneous polynomialKakeya settabulationfinite vector spaceBesicovitch setpolynomial evaluationfermionant

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Data structures (68P05) Determinants, permanents, traces, other special matrix functions (15A15) Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants
• Determinant versus permanent: salvation via generalization?
• Fast polynomial factorization and modular composition
• Fast multivariate multi-point evaluation revisited
• Counting Value Sets: Algorithm and Complexity

Cites work

• scientific article; zbMATH DE number 1303711 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• Algebraic methods for interactive proof systems
• An improved lower bound on the size of Kakeya sets over finite fields
• An introduction to geometric complexity theory
• Below all subsets for some permutational counting problems
• Computing and Combinatorics
• Computing the permanent modulo a prime power
• Directed Hamiltonicity and out-branchings via generalized Laplacians
• Fast polynomial factorization and modular composition
• Faster exponential-time algorithms in graphs of bounded average degree
• How proofs are prepared at Camelot (extended abstract)
• Introduction to analytic and probabilistic number theory. Transl. from the 3rd French edition by Patrick D. F. Ion
• Kakeya-type sets in finite vector spaces
• Modern computer algebra
• On the size of Kakeya sets in finite vector spaces
• Restriction and Kakeya phenomena for finite fields
• Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
• The complexity of computing the permanent
• The complexity of the fermionant and immanants of constant width

Cited in

(2)

• Computing permanents and counting Hamiltonian cycles by listing dissimilar vectors
• Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

This page was built for publication: Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111865)