2 citations · 2 across the 2 of their papers we have counts for
4 papers
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…
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 \…
Pseudodeterministic Algorithms and the Structure of Probabilistic Time
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
We connect the study of pseudodeterministic algorithms to two major open problems about the structural complexity of : proving hierarchy theorems and showing the e…
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2
The class consists of Boolean functions computable by size- de Morgan formulas whose leaves are any Boolean functions from a class .…