Computable structure theory can be used to study the computational complexities of classes of countable graphs. Many of these classes are well studied in computer science, where only finite graphs are considered. Our long-term goal is to check whether the complexity dividing lines in the finite setting hold in the countable setting. In the finite setting, we may consider a class complex if it is graph-isomorphism (GI) complete, which means that maximal time is needed to check if two finite graphs in the class are isomorphic. In the countable setting, we may consider a class complex if it is universal under effective bi-interpretabilty, which means that one can effectively code any given countable graph G as a graph H in the class and also effectively recover G from H. We can thus ask whether a graph class is GI-complete if and only if it is universal. As a starting point, we may restrict our study to classes of the form freebi(F), which is the class of bipartite graphs that cannot embed some fixed finite graph F as an induced subgraph. We may also consider classes of general graphs that forbid the embedding of up to two fixed finite graphs. If time permits, we may even consider other notions of complexities in addition to universality, such as Borel completeness or listability.
The theory of algorithmic information and, in particular, algorithmic fractal dimension has become an important tool in geometric measure theory through the celebrated point to set principle (PSP), which states that Hausdorff dimension is exactly effective dimension when relativized to a particular oracle. Classical results on Hausdorff dimension can now be proven using only information theory (Kolmogorov complexity). This project will focus on the study of the oracle in the PSP and on finding the most general class of sets for which this oracle is well behaved. If time allows, we will compare different levels of effectivization and the PSP.
Propositional proof complexity, emerging as a distinct field, was primarily developed to tackle fundamental open problems in computational complexity. While classical proof systems have been extensively studied, recent efforts have focused on the complexity of proofs in non-classical logics due to their diverse applications, expressive power, and critical role in computer science. Understanding the inherent complexity of proofs in non-classical logics is crucial, especially considering how lower bounds on proof lengths affect the efficiency of proof search algorithms. This project will address open problems on leveraging the study of the proof complexity of proof systems for substructural logics and superbasic logic, and hence a wide-ranging class of proof systems.