The complexity of meta-computational problems - Rajgopal, N (2020)
This thesis focuses on problems which themselves encode questions about circuits or algorithms, also called meta-computational problems. The thesis is centered on meta-computational problems like C-MCSP (minimum circuit size problem), C-Learnability and C-Satisfiability, for some circuit class C. We study mathematical questions pertaining to such problems, and their deep connections to the theory of lower bounds, which is a general theme that has attracted a lot of interest in recent years among complexity theorists.