One-way Functions and Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions.
Yanyi LiuRafael PassPublished in: Electron. Colloquium Comput. Complex. (2023)
Keyphrases
- kolmogorov complexity
- inductive inference
- probability functions
- probability distribution
- information theoretic
- complexity measures
- np hard
- random variables
- bayesian networks
- uncertain data
- continuous functions
- probabilistic model
- computational complexity
- decision trees
- mixture distributions
- parametric family
- neural network
- learning theory
- posterior probability
- conditional probabilities
- np complete
- lower bound
- machine learning