Counting Value Sets: Algorithm and Complexity
From MaRDI portal
Publication:2949496
zbMath1344.11084arXiv1111.1224MaRDI QIDQ2949496
Qi Cheng, Joshua E. Hill, Daqing Wan
Publication date: 1 October 2015
Full work available at URL: https://arxiv.org/abs/1111.1224
finite fieldpolynomial timesparse polynomialpoint countingstraight-line programsubset sum problemNP-hard, \#P-hardpolynomial value set cardinalityrandomized polynomial timeRP-reduction
Number-theoretic algorithms; complexity (11Y16) Polynomials over finite fields (11T06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (4)
Deep holes in Reed-Solomon codes based on Dickson polynomials ⋮ Counting subset sums of finite Abelian groups ⋮ Moment subset sums over finite fields ⋮ Sublinear Root Detection and New Hardness Results for Sparse Polynomials over Finite Fields
This page was built for publication: Counting Value Sets: Algorithm and Complexity