Project acronym CUTACOMBS
Project Cuts and decompositions: algorithms and combinatorial properties
Researcher (PI) Marcin PILIPCZUK
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE6, ERC-2016-STG
Summary In this proposal we plan to extend mathematical foundations of algorithms for various variants of the minimum cut problem within theoretical computer science.
Recent advances in understanding the structure of small cuts and tractability of cut problems resulted in a mature algorithmic toolbox for undirected graphs under the paradigm of parameterized complexity. In this position, we now aim at a full understanding of the tractability of cut problems in the more challenging case of directed graphs, and see opportunities to apply the aforementioned successful structural approach to advance on major open problems in other paradigms in theoretical computer science.
The specific goals of the project are grouped in the following three themes.
Directed graphs. Chart the parameterized complexity of graph separation problems in directed graphs and provide a fixed-parameter tractability toolbox, equally deep as the one in undirected graphs. Provide tractability foundations for routing problems in directed graphs, such as the disjoint paths problem with symmetric demands.
Planar graphs. Resolve main open problems with respect to network design and graph separation problems in planar graphs under the following three paradigms: parameterized complexity, approximation schemes, and cut/flow/distance sparsifiers. Recently discovered connections uncover significant potential in synergy between these three algorithmic approaches.
Tree decompositions. Show improved tractability of graph isomorphism testing in sparse graph classes. Combine the algorithmic toolbox of parameterized complexity with the theory of minimal triangulations to advance our knowledge in structural graph theory, both pure (focused on the Erdos-Hajnal conjecture) and algorithmic (focused on the tractability of Maximum Independent Set and 3-Coloring).
Summary
In this proposal we plan to extend mathematical foundations of algorithms for various variants of the minimum cut problem within theoretical computer science.
Recent advances in understanding the structure of small cuts and tractability of cut problems resulted in a mature algorithmic toolbox for undirected graphs under the paradigm of parameterized complexity. In this position, we now aim at a full understanding of the tractability of cut problems in the more challenging case of directed graphs, and see opportunities to apply the aforementioned successful structural approach to advance on major open problems in other paradigms in theoretical computer science.
The specific goals of the project are grouped in the following three themes.
Directed graphs. Chart the parameterized complexity of graph separation problems in directed graphs and provide a fixed-parameter tractability toolbox, equally deep as the one in undirected graphs. Provide tractability foundations for routing problems in directed graphs, such as the disjoint paths problem with symmetric demands.
Planar graphs. Resolve main open problems with respect to network design and graph separation problems in planar graphs under the following three paradigms: parameterized complexity, approximation schemes, and cut/flow/distance sparsifiers. Recently discovered connections uncover significant potential in synergy between these three algorithmic approaches.
Tree decompositions. Show improved tractability of graph isomorphism testing in sparse graph classes. Combine the algorithmic toolbox of parameterized complexity with the theory of minimal triangulations to advance our knowledge in structural graph theory, both pure (focused on the Erdos-Hajnal conjecture) and algorithmic (focused on the tractability of Maximum Independent Set and 3-Coloring).
Max ERC Funding
1 228 250 €
Duration
Start date: 2017-03-01, End date: 2022-02-28
Project acronym PAAL
Project Practical Approximation Algorithms
Researcher (PI) Piotr Sankowski
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary The goal of this proposal is the development and study of practical approximation algorithms. We will base our study on
theoretical models that can describe requirements for algorithms that make them practically efficient. We plan to develop an
efficient and useful programming library of approximation algorithms.
Our research on approximation algorithms will be concentrated on two main topics:
- multi-problem optimization, when the solution has to be composed out of different problems that need to interact,
- interplay between regular and random structure of network that could allow construction of good approximation algorithms.
The above concepts try to capture the notion of effective algorithms. It has to be underlined that they were not studied before.
The practical importance of these problems will be verified by the accompanying work on generic programming concepts
for approximation algorithms. These concepts will form the basis of universal library that will include Web algorithms and
algorithms for physical applications.
Summary
The goal of this proposal is the development and study of practical approximation algorithms. We will base our study on
theoretical models that can describe requirements for algorithms that make them practically efficient. We plan to develop an
efficient and useful programming library of approximation algorithms.
Our research on approximation algorithms will be concentrated on two main topics:
- multi-problem optimization, when the solution has to be composed out of different problems that need to interact,
- interplay between regular and random structure of network that could allow construction of good approximation algorithms.
The above concepts try to capture the notion of effective algorithms. It has to be underlined that they were not studied before.
The practical importance of these problems will be verified by the accompanying work on generic programming concepts
for approximation algorithms. These concepts will form the basis of universal library that will include Web algorithms and
algorithms for physical applications.
Max ERC Funding
1 000 000 €
Duration
Start date: 2010-11-01, End date: 2015-10-31
Project acronym RNA+P=123D
Project Breaking the code of RNA sequence-structure-function relationships: New strategies and tools for modelling and engineering of RNA and RNA-protein complexes
Researcher (PI) Janusz Marek Bujnicki
Host Institution (HI) INTERNATIONAL INSTITUTE OF MOLECULAR AND CELL BIOLOGY
Call Details Starting Grant (StG), LS2, ERC-2010-StG_20091118
Summary Ribonucleic acid (RNA) is a large class of macromolecules that plays a key role in the communication of biological information between DNA and proteins. RNAs have been also shown to perform enzymatic catalysis. Recently, numerous new RNAs have been identified and shown to perform essential regulatory roles in cells.
As with proteins, the function of RNA depends on its structure, which in turn is encoded in the linear sequence. The secondary structure of RNA is defined by canonical base pairs, while the tertiary (3D) structure is formed mostly by non-canonical base pairs that form three-dimensional motifs. RNA is similar to proteins in that the development of methods for 3D structure prediction is absolutely essential to functionally interpret the information encoded in the primary sequence of genes. For proteins there are many freely available methods for automated protein 3D structure prediction that produce reasonably accurate and useful models. There are also methods for objective assessment of the protein model quality. However, there are no such methods for automated 3D structure modelling of RNA. There are only methods for RNA secondary structure prediction and a few methods for manual 3D modelling, but no automated methods for comparative modelling, fold-recognition of RNA, and evaluation of models. Only recently a few methods for de novo folding of RNA appeared, but they can provide useful models only for very short molecules.
Recently, inspired by methodology for protein modelling, we have developed prototype tools for both comparative (template-based) and de novo (template-free) modelling of RNA, which allow for building models for very large RNA molecules. These tools will be further optimized and tested. The major goal is to developed tools for RNA modelling to the level of existing protein-modelling methods and to combine RNA and protein-centric methods to allow multiscale modelling of protein-nucleic acid complexes, either with or without the aid of experimental data. This proposal also includes the development of methods for the assessment of model quality and benchmarking of methods. The software tools and the theoretical predictions will be extensively tested (also by experimental verification of models), optimized and applied to biologically and medically relevant RNAs and complexes.
In one sentence: The aim of this project is to use bioinformatics and experimental methods to crack the code of sequence-structure relationships in RNA and RNA-protein complexes and to revolutionise the field of RNA & RNP modelling and structure/function analyses.
Summary
Ribonucleic acid (RNA) is a large class of macromolecules that plays a key role in the communication of biological information between DNA and proteins. RNAs have been also shown to perform enzymatic catalysis. Recently, numerous new RNAs have been identified and shown to perform essential regulatory roles in cells.
As with proteins, the function of RNA depends on its structure, which in turn is encoded in the linear sequence. The secondary structure of RNA is defined by canonical base pairs, while the tertiary (3D) structure is formed mostly by non-canonical base pairs that form three-dimensional motifs. RNA is similar to proteins in that the development of methods for 3D structure prediction is absolutely essential to functionally interpret the information encoded in the primary sequence of genes. For proteins there are many freely available methods for automated protein 3D structure prediction that produce reasonably accurate and useful models. There are also methods for objective assessment of the protein model quality. However, there are no such methods for automated 3D structure modelling of RNA. There are only methods for RNA secondary structure prediction and a few methods for manual 3D modelling, but no automated methods for comparative modelling, fold-recognition of RNA, and evaluation of models. Only recently a few methods for de novo folding of RNA appeared, but they can provide useful models only for very short molecules.
Recently, inspired by methodology for protein modelling, we have developed prototype tools for both comparative (template-based) and de novo (template-free) modelling of RNA, which allow for building models for very large RNA molecules. These tools will be further optimized and tested. The major goal is to developed tools for RNA modelling to the level of existing protein-modelling methods and to combine RNA and protein-centric methods to allow multiscale modelling of protein-nucleic acid complexes, either with or without the aid of experimental data. This proposal also includes the development of methods for the assessment of model quality and benchmarking of methods. The software tools and the theoretical predictions will be extensively tested (also by experimental verification of models), optimized and applied to biologically and medically relevant RNAs and complexes.
In one sentence: The aim of this project is to use bioinformatics and experimental methods to crack the code of sequence-structure relationships in RNA and RNA-protein complexes and to revolutionise the field of RNA & RNP modelling and structure/function analyses.
Max ERC Funding
1 500 000 €
Duration
Start date: 2011-01-01, End date: 2015-12-31
Project acronym SOSNA
Project Expressive Power of Tree Logics
Researcher (PI) Mikolaj Bojanczyk
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE6, ERC-2009-StG
Summary Logics for expressing properties of labeled trees and forests figure importantly in several different areas of Computer Science, including verification (branching temporal logics) and database theory (many XML query languages). The goal of this project is to investigate the expressive power of tree logics, mainly those logics that can be captured by tree automata. A similar study, but for word languages, is one of the main lines of research in formal language theory. The study of the expressive power of word logics has lead to many beautiful and fundamental results, including Schutzenberger's characterization of star-free languages, and the Krohn-Rhodes decomposition theorem. We intend to extend this research for trees. The type of questions we want to answer is: what is the expressive power of first-order logic in trees? is there a Krohn-Rhodes decomposition theory for trees? what is a tree group? We expect that our study of tree logics will use algebraic techniques, possibly the setting of forest algebra (as introduced by the principal investigator and Igor Walukiewicz). We would also like to extend the algebraic setting beyond regular languages of finite trees, to e.g. infinite trees, or nonregular languages.
Summary
Logics for expressing properties of labeled trees and forests figure importantly in several different areas of Computer Science, including verification (branching temporal logics) and database theory (many XML query languages). The goal of this project is to investigate the expressive power of tree logics, mainly those logics that can be captured by tree automata. A similar study, but for word languages, is one of the main lines of research in formal language theory. The study of the expressive power of word logics has lead to many beautiful and fundamental results, including Schutzenberger's characterization of star-free languages, and the Krohn-Rhodes decomposition theorem. We intend to extend this research for trees. The type of questions we want to answer is: what is the expressive power of first-order logic in trees? is there a Krohn-Rhodes decomposition theory for trees? what is a tree group? We expect that our study of tree logics will use algebraic techniques, possibly the setting of forest algebra (as introduced by the principal investigator and Igor Walukiewicz). We would also like to extend the algebraic setting beyond regular languages of finite trees, to e.g. infinite trees, or nonregular languages.
Max ERC Funding
799 920 €
Duration
Start date: 2009-11-01, End date: 2014-10-31
Project acronym TOTAL
Project Technology transfer between modern algorithmic paradigms
Researcher (PI) Marek Adam Cygan
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), PE6, ERC-2015-STG
Summary The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by now developed, they have grown mostly on their own. In our opinion the two fields have critical mass allowing for synergy effects to appear when using techniques from one area to obtain results in the other, which is the main theme of the project.
Furthermore, practical effectiveness of randomized local search heuristics is a not yet understood phenomenon. We believe that substantial increase of our understanding of superpolynomial running times in recent years should allow for rigorous proofs of parameterized and approximation results obtained by those methods.
Based on our experience with parameterized complexity and approximation algorithms we propose three research directions with potential of solving major long-standing open problems in both areas with the following objectives.
(a) Transfer from Approximation to FPT: use the PCP theorem to prove lower bounds for exact parameterized algorithms under the Exponential Time Hypothesis and take advantage of extended formulations in FPT branching algorithms.
(b) Transfer from FPT to Approximation: utilize parameterized algorithms tools in local-search-based approximation algorithms and explore the potential of proving new inapproximability results based on the Exponential Time Hypothesis.
(c) Rigorous Analysis of Practical Heuristics: unravel the practical effectiveness of randomized local search heuristics by proving their parameterized and approximation properties, when given subexponential or even moderately exponential running time.
Our objectives lie in the frontier of fixed parameter tractability and approximation areas. Complete resolution of our goals would dramatically change our understanding of both areas, with further consequences in other disciplines within computer science.
Summary
The two most recognized algorithmic paradigms of dealing with NP-hard problems in theoretical computer science nowadays are approximation algorithms and fixed parameter tractability (FPT). Despite the fact that both fields are by now developed, they have grown mostly on their own. In our opinion the two fields have critical mass allowing for synergy effects to appear when using techniques from one area to obtain results in the other, which is the main theme of the project.
Furthermore, practical effectiveness of randomized local search heuristics is a not yet understood phenomenon. We believe that substantial increase of our understanding of superpolynomial running times in recent years should allow for rigorous proofs of parameterized and approximation results obtained by those methods.
Based on our experience with parameterized complexity and approximation algorithms we propose three research directions with potential of solving major long-standing open problems in both areas with the following objectives.
(a) Transfer from Approximation to FPT: use the PCP theorem to prove lower bounds for exact parameterized algorithms under the Exponential Time Hypothesis and take advantage of extended formulations in FPT branching algorithms.
(b) Transfer from FPT to Approximation: utilize parameterized algorithms tools in local-search-based approximation algorithms and explore the potential of proving new inapproximability results based on the Exponential Time Hypothesis.
(c) Rigorous Analysis of Practical Heuristics: unravel the practical effectiveness of randomized local search heuristics by proving their parameterized and approximation properties, when given subexponential or even moderately exponential running time.
Our objectives lie in the frontier of fixed parameter tractability and approximation areas. Complete resolution of our goals would dramatically change our understanding of both areas, with further consequences in other disciplines within computer science.
Max ERC Funding
1 417 625 €
Duration
Start date: 2016-04-01, End date: 2021-03-31
