Improved classical and quantum algorithms for subset-sum
From MaRDI portal
Recommendations
- The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
- Quantum algorithms for the subset-sum problem
- Improved low-memory subset sum and LPN algorithms via multiple collisions
- Optimal merging in quantum k-xor and k-sum algorithms
- Low weight discrete logarithm and subset sum in \(2^{0.65n}\) with polynomial memory
Cites work
- A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
- Another Subexponential-time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Computing Partitions with Applications to the Knapsack Problem
- Decoding Random Binary Linear Codes in 2 n/20: How 1 + 1 = 0 Improves Information Set Decoding
- Decoding random linear codes in \(\tilde{\mathcal{O}}(2^{0.054n})\)
- Finding shortest lattice vectors faster using quantum search
- Hidden shift quantum cryptanalysis and implications
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 2103524 (Why is no real title available?)
- Improved Generic Algorithms for Hard Knapsacks
- New generic algorithms for hard knapsacks
- On computing nearest neighbors with applications to decoding of binary linear codes
- Optimal merging in quantum k-xor and k-sum algorithms
- Public-Key Cryptographic Primitives Provably as Secure as Subset Sum
- Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
- Quantum algorithms for the subset-sum problem
- Quantum information set decoding algorithms
- Quantum search with variable times
- Quantum security analysis of CSIDH
- Quantum Walk Algorithm for Element Distinctness
- Search via Quantum Walk
- Strengths and Weaknesses of Quantum Computing
- Ternary Syndrome Decoding with large weight
- The Double Dixie Cup Problem
- The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound
Cited in
(30)- Quantum key search for ternary LWE
- Optimal merging in quantum k-xor and k-sum algorithms
- How to meet ternary LWE keys
- MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications
- Improved low-memory subset sum and LPN algorithms via multiple collisions
- scientific article; zbMATH DE number 5320343 (Why is no real title available?)
- Quantum algorithms for the subset-sum problem
- Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
- Subset Sum Quantumly in 1.17 n .
- Lattice Sieving via Quantum Random Walks
- Finding many collisions via reusable quantum walks. Application to lattice sieving
- New time-memory trade-offs for subset sum -- improving ISD in theory and practice
- Quantum speedup for solving the minimum vertex cover problem based on Grover search algorithm
- Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection
- Time and Query Complexity Tradeoffs for the Dihedral Coset Problem
- Low memory attacks on small key CSIDH
- Commitments with efficient zero-knowledge arguments from subset sum problems
- Revisiting nearest-neighbor-based information set decoding
- Memory-efficient attacks on small LWE keys
- Memory-efficient attacks on small LWE keys
- Improved quantum algorithms for the k-XOR problem
- CryptAttackTester: high-assurance attack analysis
- Improved alternating-moduli PRFs and post-quantum signatures
- A faster algorithm for pigeonhole equal sums
- Reducing the number of qubits in solving LWE
- Classical and quantum algorithms for variants of subset-sum via dynamic programming
- A hybrid of lattice-reduction and Meet-LWE via near-collision on Babai's plane
- Quantum collision search for ternary LWE keys
- New algorithms for pigeonhole equal subset sum
- Designs for practical SHE schemes based on Ring-LWR
This page was built for publication: Improved classical and quantum algorithms for subset-sum
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2692398)
