A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
From MaRDI portal
Publication:3912012
DOI10.1137/0210033zbMath0462.68015OpenAlexW1984481156MaRDI QIDQ3912012
Richard Schroeppel, Adi Shamir
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210033
Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60) Discrete mathematics in relation to computer science (68R99)
Related Items
The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound ⋮ Average polynomial time complexity of some NP-complete problems ⋮ An efficient pruning algorithm for value independent knapsack problem using a DAG structure ⋮ Polynomial-average-time satisfiability problems ⋮ An \(O(n^{lg\,k}\cdot 2^{n/2})\) time and \(O(k\cdot 2^{n/k})\) space algorithm for certain NP-complete problems ⋮ An optimal and scalable parallelization of the two-list algorithm for the subset-sum problem ⋮ Largest chordal and interval subgraphs faster than \(2^n\) ⋮ Partition into triangles on bounded degree graphs ⋮ Refined cryptanalysis of the GPRS ciphers GEA-1 and GEA-2 ⋮ Time-Memory Tradeoffs for Large-Weight Syndrome Decoding in Ternary Codes ⋮ Lattice-based algorithms for number partitioning in the hard phase ⋮ New time-memory trade-offs for subset sum -- improving ISD in theory and practice ⋮ New Definition of Density on Knapsack Cryptosystems ⋮ Zero-knowledge protocols for the subset sum problem from MPC-in-the-head with rejection ⋮ A non-heuristic approach to time-space tradeoffs and optimizations for BKW ⋮ Asymptotic results for the number of Wagner's solutions to a generalised birthday problem ⋮ An algebraic expression of the number partitioning problem ⋮ Improved classical and quantum algorithms for subset-sum ⋮ Correspondence principle as equivalence of categories ⋮ Unnamed Item ⋮ The complexity of searching in \(X+Y\) and other multisets ⋮ Improved combinatorial algorithms for the inhomogeneous short integer solution problem ⋮ On the connection between Hamming codes, Heapsort and other methods ⋮ An Improved Multi-set Algorithm for the Dense Subset Sum Problem ⋮ A low-memory algorithm for finding short product representations in finite groups. ⋮ Improved algorithms for the general exact satisfiability problem ⋮ Subset Sum Quantumly in 1.17 n . ⋮ Open problems around exact algorithms ⋮ An algorithmic framework for the generalized birthday problem ⋮ Efficient dissection of bicomposite problems with cryptanalytic applications ⋮ Unnamed Item ⋮ New algorithms for exact satisfiability ⋮ On the minimum gap between sums of square roots of small integers ⋮ Sort and Search: exact algorithms for generalized domination ⋮ A mixed-integer linear programming model to solve the multidimensional multi-way number partitioning problem ⋮ Improved attacks on knapsack problem with their variants and a knapsack type ID-scheme ⋮ Faster Space-Efficient Algorithms for Subset Sum, $k$-Sum, and Related Problems ⋮ Cryptanalysis of the GPRS encryption algorithms GEA-1 and GEA-2 ⋮ A complete anytime algorithm for number partitioning ⋮ Improved simulation of nondeterministic Turing machines ⋮ Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems ⋮ Moderate exponential-time algorithms for scheduling problems ⋮ Faster exact solutions for some NP-hard problems. ⋮ A new algorithm for optimal 2-constraint satisfaction and its implications ⋮ Combinatorial analysis (nonnegative matrices, algorithmic problems) ⋮ On space-efficient algorithms for certain NP-complete problems ⋮ Optimal merging in quantum \(k\)-xor and \(k\)-sum algorithms ⋮ He gives C-sieves on the CSIDH ⋮ Quantum security analysis of CSIDH
