Kolmogorov complexity characterizes Statistical Zero Knowledge

Abstract: Kolmogorov Complexity is an important notion of randomness in computability theory. Along with the Minimum Circuit Size problem (MCSP), it constitutes Meta-Complexity theory – the study of complexity of computational problems that are themselves about (some measure of) complexity. We will discuss a brief history of attempts to characterize Kolmogorov complexity that culminate in a successful characterization of Statistical Zero Knowledge (SZK) and its non-interactive counterpart NISZK. We will also discuss a potential avenue of attacking NP vs NL as an application of this result.

(We will assume zero knowledge about these classes or Kolmogorov Complexity)

This is based on joint work with Eric Allender and Shuichi Hirahara