The Planted k-SUM Problem: Algorithms, Lower Bounds, Hardness Amplification, and Cryptography.
Sagnik SahaNikolaj Ignatieff SchwartzbachPrashant Nalini VasudevanPublished in: IACR Cryptol. ePrint Arch. (2023)
Keyphrases
- lower bound
- upper and lower bounds
- worst case
- computational complexity
- significant improvement
- np hard
- learning algorithm
- machine learning algorithms
- times faster
- orders of magnitude
- data structure
- computational cost
- average case
- machine learning
- phase transition
- cellular automata
- benchmark datasets
- upper bound
- evolutionary algorithm
- objective function