73 citations · 222 across the 11 of their papers we have counts for
5 papers · 1 filter
Structural Complexity of Rational Interactive Proofs
Daniil Musatov, Georgii Potapov
This is the full version of a paper submitted to the Computability in Europe (CiE 2023) conference, with all proofs omitted there. In 2012 P. D. Azar and S. Micali introduced a new…
Space-Bounded Kolmogorov Extractors
Daniil Musatov
An extractor is a function that receives some randomness and either "improves" it or produces "new" randomness. There are statistical and algorithmical specifications of this notio…
Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization
Daniil Musatov
Many theorems about Kolmogorov complexity rely on existence of combinatorial objects with specific properties. Usually the probabilistic method gives such objects with better param…
Variations on Muchnik's Conditional Complexity Theorem
Daniil Musatov, Andrei Romashchenko, Alexander Shen
Muchnik's theorem about simple conditional descriptions states that for all strings and there exists a short program transforming to that has the least possible…
Extractors and an efficient variant of Muchnik's theorem
Daniil Musatov
Muchnik's theorem about simple conditional descriprion states that for all words and there exists a short program transforming to that has the least possible le…