Invited Speaker

There will be an invited talk by Akinori Kawachi (Department of Mathematical and Computing Sciences, Tokyo Institute of Technology).

Title: Circuit Lower Bounds from Learning-Theoretic Approaches

Abstract. Proving circuit lower bounds in uniform classes is one of the most significant goals in the computational complexity theory. Recently, the so-called "algorithmic approaches" for circuit lower bounds have attracted interest so much since Williams' result of the separation between NEXP and ACC0 using fast Circuit SAT algorithms. In this talk, we review how techniques for learning circuits are useful to prove circuit lower bounds as one of the algorithmic approaches.

Last update June 14, 2013