One-Way Functions and the Hardness of (Probabilistic) Time-Bounded Kolmogorov Complexity w.r.t. Samplable Distributions
Yanyi Liu, Rafael Pass
Topics & Concepts
Bounded functionKolmogorov complexityEquivalence (formal languages)Probabilistic logicCombinatoricsDiscrete mathematicsMathematicsDistribution (mathematics)Uniform boundednessMathematical analysisStatisticsComputability, Logic, AI AlgorithmsBenford’s Law and Fraud DetectionComplexity and Algorithms in Graphs