The relationship between graph theory and logic will be the subject of the research conducted by Prof. Szymon Toruńczyk from the UW’s Faculty of Mathematics, Informatics and Mechanics as part of the project Limits of structural tractability (BUKA). Prof. Toruńczyk was awarded the Consolidator Grant given by the European Research Council.
In the project Limits of structural tractability, with funding of €1.94 mln, Prof. Toruńczyk will focus on the logical structure of graphs.
“A graph is a network of connected objects. Graphs are ubiquitous in computer science, because they can be used to describe different types of networks, such as social network, the World Wide Web, rail, air and road networks or other various databases. That is why, algorithms that manipulate graphs play a very important role in the field of computer science,” Prof. Toruńczyk explains.
The aim of the project is to prove mathematical theorems that define the theoretical capabilities of algorithms performing computations on graphs. For this purpose, theoretical tools will be used, covering different areas of mathematics and theoretical computer science, such as logic, algorithmics or combinatorics.
Mathematical theory
“The fundamental matter is to understand how quickly – theoretically – various properties described by logic can be computed on graphs. In my research, I am trying to find out what structural properties of the studied graphs ensure that certain algorithmic problems can be solved quickly on the considered graphs,” Prof. Toruńczyk emphasises.
The expected result of the study is to develop the mathematical theory which will consist of definitions, theorems and proofs, together describing the theoretical limits of the possibilities of efficient algorithms performing certain types of computations on graphs related to logic.
“In the project, we need to invent and develop new graph parameters. These are measurable numerical parameters that describe the complexity of the considered graph,” Prof. Toruńczyk says.
The project will start in October 2024 and will last five years.
ERC Consolidator Grants
On 23rd November, the European Research Council (ERC) published the results of the call for Consolidator Grants. The grants are intended for successful researchers, with 7 to 12 years of experience since completion of doctoral studies. Researchers from the UW have so far received eleven Consolidator Grants.
Prof. Szymon Toruńczyk graduated from the UW’s Faculty of Mathematics, Informatics and Mechanics, where he was also awarded a doctoral degree in 2011. For his doctoral dissertation he received the Ackermann Award granted by the European Association for Computer Science Logic. The award is given for outstanding dissertations, which focus on logic in computer science. The researcher completed postdoctoral fellowships at The École Normale Supérieure (ENS Cachan) and Universitat Politècnica de Catalunya in Barcelona. Prof. Toruńczyk’s publications have been presented at prestigious conferences on theoretical computer science.