Worst-Case Hardness for LPN and Cryptographic Hashing via Code Smoothing.
Zvika BrakerskiVadim LyubashevskyVinod VaikuntanathanDaniel WichsPublished in: Electron. Colloquium Comput. Complex. (2018)
Keyphrases
- worst case
- hash functions
- binary codes
- np hard
- upper bound
- average case
- greedy algorithm
- lower bound
- source code
- approximation algorithms
- error bounds
- smart card
- data structure
- hashing algorithm
- running times
- similarity search
- worst case analysis
- smoothing methods
- worst case scenario
- space complexity
- random projections
- nearest neighbor search
- video copy detection
- order preserving
- locality sensitive hashing
- special case
- key management
- data distribution
- open source
- language model
- range queries