Algebraic algorithms for variants of subset sum

DOI10.1007/978-3-030-95018-7_19OpenAlexW4206995494MaRDI QIDQ6102280

Pranjal Dutta, Mahesh Sreekumar Rajasree

Publication date: 8 May 2023

Published in: Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-030-95018-7_19

zbMATH Keywords

interpolationpower seriesHamming weightsubset sumNewton's identitieslogspaceisolation lemma

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Related Items (1)

Efficient reductions and algorithms for subset product

Cites Work

• Unnamed Item
• Unnamed Item
• On a distribution property of the residual order of \(a\pmod p\). I
• A remark on Artin's conjecture
• On the deterministic complexity of factoring polynomials over finite fields
• Matching is as easy as matrix inversion
• Threshold circuits of small majority-depth
• On finding primitive roots in finite fields
• PRIMES is in P
• Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
• Chosen-Ciphertext Security from Subset Sum
• Modern Computer Algebra
• Saving space by algebraization
• Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
• A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum
• Artin's Primitive Root Conjecture – A Survey
• Quantum Algorithms for the Subset-Sum Problem
• Linear Time Algorithms for Knapsack Problems with Bounded Weights
• Faster Pseudopolynomial Time Algorithms for Subset Sum
• Quadratic Time-Space Lower Bounds for Computing Natural Functions with a Random Oracle
• Randomness efficient identity testing of multivariate polynomials
• SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
• Character sums and deterministic polynomial root finding in finite fields
• On the interval containing at least one prime number

This page was built for publication: Algebraic algorithms for variants of subset sum