logo
ProjectForthcoming

Descriptive Complexity in the Finite and Infinite

Forthcoming · Hungary

Source: EU Funding & Tenders Portal

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 Bo

Status
Prospective
Sector
Government
Location
Hungary
Updated
19 Nov 2026
Source
EU Funding & Tenders Portal

ConstructChat

Ask ConstructChat about Descriptive Complexity in the Finite and Infinite

Pick a question to edit it, or write your own.

First answer free · no account

I am a

Project Information FAQ

Project Information

4 Q
The project “Descriptive Complexity in the Finite and Infinite” is an infrastructure initiative in the Government sector, located in Hungary. Taiyo aggregates data on it from EU Funding & Tenders Portal.

Participants

Sponsoring Agency

Status

Original status

forthcoming

Taiyo status

Prospective

Taiyo last update

2026-11-19

Contact

Not available for this record.

Description

Description

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.

Location

Country

Hungary

Source

Source

EU Funding & Tenders Portal

URL

More Details

Record type

Project

Sector

Government

Article published date

2026-02-01

More on this project

Research

Free account

View all details

You are reading the public part. A free account opens the rest:

  • Every detail on this project
  • News and media coverage
  • Technical research
View all details

Free account · no card · lands you back on this project