Meta-complexity refers to the study of complexity of problems that are themselves about computational complexity. The canonical meta-complexity problem in the Boolean world is MCSP (Minimum Circuit Size Problem).

We consider two-player stochastic games on a graph. Two-player stochastic games are a generalization of  two-player games and Markov decision processes. Each state in the graph is controlled by one of the two players P1 and P2.

In this thesis defense, we will discuss the following results.

Partial function extension is a basic problem that underpins multiple research topics in optimization, including learning, property testing, and game theory.

Algebraic Complexity Theory is a field in which one studies complexity theoretic questions surrounding algebraic objects. In this talk we will be broadly discussing two such problems.