Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Hungary

European Research Council grant · Running

DEFINE Descriptive Complexity in the Finite and Infinite

Coordinator
Eotvos Lorand Tudomanyegyetem, Hungary
Runs
1 September 2026 to 31 August 2031
Status
Running
EU funding
€1.9m
Total cost
€1.9m
Partners
1 organisations in 1 countries
Type
European Research Council grant
Grant agreement
101231345

What the project is doing

In the project's own words, from its summary on CORDIS.

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, and transferring theorems from descriptive set theory to this context.

Through this research, we will achieve a deeper understanding of complexity hierarchies arising from CSPs, further advance the field of descriptive combinatorics, and transfer techniques between the finite and infinite worlds.

Topics

Who is involved

OrganisationCityCountryRole
Eotvos Lorand TudomanyegyetemBudapestHungaryCoordinator

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI