Cryptography from Sublinear-Time Average-Case Hardness of Time-Bounded Kolmogorov Complexity.
Yanyi LiuRafael PassPublished in: Electron. Colloquium Comput. Complex. (2021)
Keyphrases
- average case
- kolmogorov complexity
- worst case
- inductive inference
- vc dimension
- worst case analysis
- complexity measures
- uniform distribution
- computational complexity
- learning curves
- average case complexity
- phase transition
- upper bound
- np hard
- lower bound
- learning theory
- pairwise
- learning experience
- small number
- machine learning