Improved Learning from Time-bounded Kolmogorov Complexity
summary
Assuming heuristics for time‑bounded Kolmogorov complexity (MKTP/KT) on average, the work gives concrete learners for P/poly that are agnostic PAC learning algorithms using only random examples and achieving distributional generality for any sampler in P/poly. Proof ingredients are reductions to random right‑hand‑side refutation, a worst‑case estimator for K^poly, a probabilistic KT compression via generator reconstruction, and a distributional inverter (Impagliazzo–Luby/Allender et al.); KT requires knowing the sampler code while K^poly needs just complexity bounds.
AI-written summary · about
chapters (10)
- 0:00Introduction
- 4:53Learning over Uniform Distribution
- 10:38Learning over Agnostic Pack
- 13:18Learning from Random Examples
- 14:51Complexity Measures
- 16:46Proofs
- 25:49Framework
- 38:18Distributional Inversion
- 42:12Open Problems
- 43:11Questions
related talks
06mStatic Delayed Sampling for Probabilistic Programming Languages
17mLazy Knowledge Compilation for Discrete PPLs
01h 10mDistribution Estimation and Applications I
26mComplete Problems for Multi-Pseudodeterministic Computations
55mLower Bounds Against PC With Extension Variables
56mEntropy, Capacity, and Counting
01h 02mConsistency of NEXP Not in P/poly in a Strong Theory
19mCompiling Probabilistic Programs for Variable Elimination with Information Flow