ERC Consolidator Grant · 2025
Descriptive Complexity in the Finite and Infinite
We propose to study infinite, definable (Borel, measurable, etc.) graphs and structures and their interplay with finite ones from the perspective of descriptive complexity. Our focus will be on the following three directions: -Determining the descriptive complexity of constraint satisfaction problems (CSPs), or, equivalently, homomorphism problems on infinite domains. -Analyzing the concept of Borel hyperfiniteness of graphs and establishing new examples of non-hyperfinite graphs using methods from infinite-dimensional Ramsey theory. -Developing finitary analogues of the Borel hierarchy from descriptive set theory, constructing generalizations of the LOCAL model of distributed computing,…
From the public funding record at EU CORDIS. Describes the funded project, not the reviews below.