Tutorial: Frontiers of Efficient PAC Learning

The main open question of meta-complexity is to determine the algorithmic complexity of the following problem: What is the circuit (time-bounded Kolmogorov) complexity of a given string? After over fifty years, it is still not known if this problem is in P, or is NP-complete. Understanding the complexity of this problem turns out to be crucial also for cryptography (the existence of one-way functions) and computational learning (Valiant's PAC learning model). This workshop will brought together researchers in meta-complexity, cryptography and learning to discuss recent progress, identify the next research goals, and start new collaborations on the promising research directions. The focus was on the connections between cryptography and learning, with meta-complexity as the bridge between the two areas. Watch Rocco Servedio's tutorial on "Frontiers of Efficient PAC Learning"!