Verbitsky O. Game-theoretic and extremal problems of combinatorics with applications in complexity theory

The thesis is devoted to problems of combinatorial game theory and extremal combinatorics, where a special attention is paid to constructibility issues and applications in computational complexity theory and descriptive complexity theory. We solve several extremal Ramsey-type problems for symmetric subsets of a Euclidean space. For the class of strong games of avoiding a forbidden subgraph we introduce and investigate the notion of a symmetric strategy. We introduce the notion of the logical depth of a graph and estimate this invariant based on a comprehensive study of the Ehrenfeucht game on graphs. Using a game modelling and reductions to extremal problems, we obtain results on parallel repetition of interactive proofs. Zero-knowledge proofs are designed for some problems on permutation groups. We establish the hardness of computing the forcing chromatic number of a graph. An oracle is constructed that answers an open question about the existence of optimal algorithms for coNP-problems posed by Krajicek and Pudlak.