30 citations · 61 across the 15 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.CC2022★ 2 cited
Theory and Applications of Probabilistic Kolmogorov Complexity
Zhenjian Lu, Igor C. Oliveira
Diverse applications of Kolmogorov complexity to learning [CIKK16], circuit complexity [OPS19], cryptography [LP20], average-case complexity [Hir21], and proof search [Kra22] have…
cs.CC2022
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
The classical coding theorem in Kolmogorov complexity states that if an -bit string is sampled with probability by an algorithm with prefix-free domain then K$(x) \leq \…