On the subset sum problem over finite fields

2007/08/18 by Jiyou Li, Daqing Wan, Li, Jiyou +1 · 7 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Coding theory and cryptography

paper · pdf · doi:10.48550/arxiv.0708.2456

Abstract

The subset sum problem over finite fields is a well-known \bf NP-complete problem. It arises naturally from decoding generalized Reed-Solomon codes. In this paper, we study the number of solutions of the subset sum problem from a mathematical point of view. In several interesting cases, we obtain explicit or asymptotic formulas for the solution number. As a consequence, we obtain some results on the decoding problem of Reed-Solomon codes.

Cited by

• When Do Subset Sums in Finite Abelian Groups Support 2-Designs?
• Deep holes of a class of twisted Reed-Solomon codes
• On decoding extended Han-Zhang codes
• On optimal quantum LRCs from the Hermitian construction and t-designs
• The extended code for a class of generalized Roth-Lempel codes and their properties
• Properties and Decoding of Twisted GRS Codes and Their Extensions
• A Bijection between Necklaces and Restricted Multisets

Related

• Moment subset sums over finite fields
• A short note on Merlin-Arthur protocols for subset sum
• An Asymptotic Formula For Counting Subset Sums Over Subgroups Of Finite Fields
• Combinatorial problems in finite fields and Sidon sets
• New Algorithms for Subset Sum Problem