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


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 timebounded 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 timebounded 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 quasipolynomial 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^{1eps}approximate algorithm for MrKtP running in randomized quasipolynomial 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.