Meta-Complexity Seminar

Join Meta-Complexity program participants in this weekly seminar.

Speaker: Halley Goldberg

Title: Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity



Abstract: It is a central and long-open problem to understand the connections between worst-case and average-case complexity, particularly of the class NP. Recently, Shuichi Hirahara (STOC 2021) made exciting progress toward this goal by applying techniques from meta-complexity. He showed, for example, that if DistΣ^P_2 ⊆ AvgP then NP ⊆ DTIME[2^{O(n/log n)}]. However, these results are non-black-box, and thus do not survive in the setting of probabilistic computation.

 

In this talk, I will discuss a recently-developed, probabilistic variant of time-bounded Kolmogorov complexity, called pK^t complexity, which allows us to overcome the above limitation. Starting from basic definitions and background, the talk will cover the proof of the following theorem: if DistΣ^P_2 ⊆ AvgBPP then AM ⊆ BPTIME[2^{O(n/log n)}].

 

Based on joint work with Valentine Kabanets, Zhenjian Lu, and Igor Oliveira.