Moment subset sums over finite fields

DOI10.1016/J.FFA.2019.101607MaRDI QIDQ2302567zbMATH OpenOpenAlexWikidataFDO

Authors Tim Lai, Alicia Marino, Angela Robinson, Daqing Wan

Publication date 26 February 2020

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1910.05894

zbMATH Keywords

Dickson polynomialWeil boundmoment subset sums

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Other character sums and Gauss sums (11T24)

Abstract: The $k$-subset sum problem over finite fields is a classical NP-complete problem.Motivated by coding theory applications, a more complex problem is the higher $m$-th moment $k$-subset sum problem over finite fields. We show that there is a deterministic polynomial time algorithm for the $m$-th moment $k$-subset sum problem over finite fields for each fixed $m$ when the evaluation set is the image set of a monomial or Dickson polynomial of any degree $n$. In the classical case $m=1$, this recovers previous findings.

Recommendations

• The \(k\)-subset sum problem over finite fields
• On the subset sum problem over finite fields
• The \(k\)-subset sum problem over finite fields of characteristic 2
• On the subset sum problem for finite fields
• On the Odlyzko-Stanley enumeration problem and Waring's problem over finite fields

Cites work

• A CLASS OF INCOMPLETE CHARACTER SUMS
• A new sieve for distinct coordinate counting
• An Almost Linear-Time Algorithm for the Dense Subset-Sum Problem
• An asymptotic formula for counting subset sums over subgroups of finite fields
• Automata, Languages and Programming
• Cayley graphs generated by small degree polynomials over finite fields
• Counting Value Sets: Algorithm and Complexity
• Deep holes in Reed-Solomon codes based on Dickson polynomials
• Introduction to algorithms.
• Mathematics and computation. A theory revolutionizing technology and science
• NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem
• On Deciding Deep Holes of Reed-Solomon Codes
• On the number of solutions of equations of Dickson polynomials over finite fields
• On the subset sum problem over finite fields
• Solving low-density subset sum problems
• The \(k\)-subset sum problem over finite fields
• The \(k\)-subset sum problem over finite fields of characteristic 2
• The complexity of theorem-proving procedures
• The intractability of computing the minimum distance of a code

Cited in

(6)

• Subset sums over Galois rings
• On the subset sum problem over finite fields
• An approach to the moments subset sum problem through systems of diagonal equations over finite fields
• Divisibility on point counting over finite Witt rings
• The \(k\)-subset sum problem over finite fields
• The \(k\)-subset sum problem over finite fields of characteristic 2

This page was built for publication: Moment subset sums over finite fields

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