COMAゼミ 2024@The University of Tokyo

It was a domestic seminar and the talk was given in Japanese. 

The slides↓

The slides with notes↓

Since the talk aimed to enhance interdisciplinary communications, some explanations of technical parts were somehow hand-wavy. Basically, the audience can easily fill in the most gaps by tackling the original literature referred to in the slides. However, there might be a few exceptions:
・For proofs of Ajtai's theorem,  the following are recommended:

Krajíček, J. (2019). Proof complexity. Cambridge, UK: Cambridge University Press, Encyclopedia of Mathematics and Its Applications 170.
Beame, P., & Riis, S. (1998). More on the relative strength of counting principles, in Proof Complexity and Feasible Arithmetics, P. Beame, & S. Buss (Eds.), DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol.39, American Mathematical Society, Providence, RI, 13-35.

・To get familiar with the treatment of VNC^{1}, see:

Cook, S., & Nguyen, P. (2010). Logical foundations of proof complexity. New York, NY: Cambridge University Press, Perspectives in Logic.