Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Igor Carboni Oliveira: Randomness and Intractability in Kolmogorov Complexity

LFCS seminar: Igor Carboni Oliveira: Randomness and Intractability in Kolmogorov Complexity

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
When May 21, 2019
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal
iCal

We introduce randomized time-bounded Kolmogorov complexity (rKt), a natural extension of Levin's notion of Kolmogorov complexity from 1984. A string w of low rKt complexity can be decompressed from a short representation via a time-bounded algorithm that outputs w with high probability.

This complexity measure gives rise to a decision problem over strings: MrKtP (The Minimum rKt Problem). We explore ideas from pseudorandomness to prove that MrKtP and its variants cannot be solved in randomized quasi-polynomial time. This exhibits a natural string compression problem that is provably intractable, even for randomized computations. Our techniques also imply that there is no n^{1-eps}-approximate algorithm for MrKtP running in randomized quasi-polynomial time.

Complementing this lower bound, we observe connections between rKt, the power of randomness in computing, and circuit complexity. In particular, we present the first hardness magnification theorem for a natural problem that is unconditionally hard against a strong model of computation.

Document Actions