Project acronym CLOUDMAP
Project Cloud Computing via Homomorphic Encryption and Multilinear Maps
Researcher (PI) Jean-Sebastien Coron
Host Institution (HI) UNIVERSITE DU LUXEMBOURG
Call Details Advanced Grant (AdG), PE6, ERC-2017-ADG
Summary The past thirty years have seen cryptography move from arcane to commonplace: Internet, mobile phones, banking system, etc. Homomorphic cryptography now offers the tantalizing goal of being able to process sensitive information in encrypted form, without needing to compromise on the privacy and security of the citizens and organizations that provide the input data. More recently, cryptographic multilinear maps have revolutionized cryptography with the emergence of indistinguishability obfuscation (iO), which in theory can been used to realize numerous advanced cryptographic functionalities that previously seemed beyond reach. However the security of multilinear maps is still poorly understood, and many iO schemes have been broken; moreover all constructions of iO are currently unpractical.
The goal of the CLOUDMAP project is to make these advanced cryptographic tasks usable in practice, so that citizens do not have to compromise on the privacy and security of their input data. This goal can only be achieved by considering the mathematical foundations of these primitives, working "from first principles", rather than focusing on premature optimizations. To achieve this goal, our first objective will be to better understand the security of the underlying primitives of multilinear maps and iO schemes. Our second objective will be to develop new approaches to significantly improve their efficiency. Our third objective will be to build applications of multilinear maps and iO that can be implemented in practice.
Summary
The past thirty years have seen cryptography move from arcane to commonplace: Internet, mobile phones, banking system, etc. Homomorphic cryptography now offers the tantalizing goal of being able to process sensitive information in encrypted form, without needing to compromise on the privacy and security of the citizens and organizations that provide the input data. More recently, cryptographic multilinear maps have revolutionized cryptography with the emergence of indistinguishability obfuscation (iO), which in theory can been used to realize numerous advanced cryptographic functionalities that previously seemed beyond reach. However the security of multilinear maps is still poorly understood, and many iO schemes have been broken; moreover all constructions of iO are currently unpractical.
The goal of the CLOUDMAP project is to make these advanced cryptographic tasks usable in practice, so that citizens do not have to compromise on the privacy and security of their input data. This goal can only be achieved by considering the mathematical foundations of these primitives, working "from first principles", rather than focusing on premature optimizations. To achieve this goal, our first objective will be to better understand the security of the underlying primitives of multilinear maps and iO schemes. Our second objective will be to develop new approaches to significantly improve their efficiency. Our third objective will be to build applications of multilinear maps and iO that can be implemented in practice.
Max ERC Funding
2 491 266 €
Duration
Start date: 2018-10-01, End date: 2023-09-30
Project acronym CULTURECONTACT
Project Europe and America in contact: a multidisciplinary study of cross-cultural transfer in the New World across time
Researcher (PI) Justyna Agnieszka Olko
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Starting Grant (StG), SH6, ERC-2012-StG_20111124
Summary "At the core of this research proposal is the aim of reconstructing and understanding the nature, exact trajectories, mechanisms and implications of cross-cultural contact and transfers between Europeans and the native people of the Americas, focusing on, but not limited to, the Nahuatl-speaking zone of central Mexico. A major innovation of this project is to study this process of cross-cultural communication in its full historical depth, through the colonial and postcolonial eras up to the present day and encompassing different stages and types of contact. The meticulous and cross-disciplinary study of an extensive body of texts in Nahuatl (“Aztec”) and Spanish, complemented by present-day ethnolinguistic data, will make it possible to deduce and understand patterns across time and space in ways novel to existing scholarship, embracing both micro- and macroregional trends. The proposed research starts with identifying transfers in language, studied systematically through the creation of extensive databases, but leads to exploring the substance of cross-cultural transfer and the essence of developments, becoming a fundamental way of studying culture and its transformations. Thus, an important aim is the correlation of language phenomena with more general contact-induced culture change, including especially evolving forms of political, social and municipal organization in the native world, where the change is more salient. Breaking existing disciplinary boundaries in the humanities, the project embraces both indigenous and European perspectives, assuming that the innovation of studying both sides in a single framework and in the proposed time span is particularly promising in dealing with a notably two-sided, prolonged historical process. The complementary lines of research, native and Spanish, are expected to highlight and make understandable factors underlying and facilitating cultural convergence between them in different aspects of colonial life and beyond."
Summary
"At the core of this research proposal is the aim of reconstructing and understanding the nature, exact trajectories, mechanisms and implications of cross-cultural contact and transfers between Europeans and the native people of the Americas, focusing on, but not limited to, the Nahuatl-speaking zone of central Mexico. A major innovation of this project is to study this process of cross-cultural communication in its full historical depth, through the colonial and postcolonial eras up to the present day and encompassing different stages and types of contact. The meticulous and cross-disciplinary study of an extensive body of texts in Nahuatl (“Aztec”) and Spanish, complemented by present-day ethnolinguistic data, will make it possible to deduce and understand patterns across time and space in ways novel to existing scholarship, embracing both micro- and macroregional trends. The proposed research starts with identifying transfers in language, studied systematically through the creation of extensive databases, but leads to exploring the substance of cross-cultural transfer and the essence of developments, becoming a fundamental way of studying culture and its transformations. Thus, an important aim is the correlation of language phenomena with more general contact-induced culture change, including especially evolving forms of political, social and municipal organization in the native world, where the change is more salient. Breaking existing disciplinary boundaries in the humanities, the project embraces both indigenous and European perspectives, assuming that the innovation of studying both sides in a single framework and in the proposed time span is particularly promising in dealing with a notably two-sided, prolonged historical process. The complementary lines of research, native and Spanish, are expected to highlight and make understandable factors underlying and facilitating cultural convergence between them in different aspects of colonial life and beyond."
Max ERC Funding
1 318 840 €
Duration
Start date: 2012-12-01, End date: 2017-11-30
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 IMMOCAP
Project 'If immortality unveil…'– development of the novel types of energy storage systems with excellent long-term performance
Researcher (PI) Krzysztof FIC
Host Institution (HI) POLITECHNIKA POZNANSKA
Call Details Starting Grant (StG), PE8, ERC-2017-STG
Summary The major goal of the project is to develop a novel type of an electrochemical capacitor with high specific power (up to 5 kW/kg) and energy (up to 20 Wh/kg) preserved along at least 50 000 cycles. Thus, completion of the project will result in remarkable enhancement of specific energy, power and life time of modern electrochemical capacitors. Advanced electrochemical testing (galvanostatic cycling with constant power loads, electrochemical impedance spectroscopy, accelerated aging and kinetic tests) will be accompanied by materials design and detailed characterization. Moreover, the project aims at the implementation of novel concepts of the electrolytes and designing of new operando technique for capacitor characterization. All these efforts aim at the development of sustainable and efficient energy conversion and storage system.
Summary
The major goal of the project is to develop a novel type of an electrochemical capacitor with high specific power (up to 5 kW/kg) and energy (up to 20 Wh/kg) preserved along at least 50 000 cycles. Thus, completion of the project will result in remarkable enhancement of specific energy, power and life time of modern electrochemical capacitors. Advanced electrochemical testing (galvanostatic cycling with constant power loads, electrochemical impedance spectroscopy, accelerated aging and kinetic tests) will be accompanied by materials design and detailed characterization. Moreover, the project aims at the implementation of novel concepts of the electrolytes and designing of new operando technique for capacitor characterization. All these efforts aim at the development of sustainable and efficient energy conversion and storage system.
Max ERC Funding
1 385 000 €
Duration
Start date: 2017-10-01, End date: 2022-09-30
Project acronym INTERACT
Project Intelligent Non-woven Textiles and Elastomeric Responsive materials by Advancing liquid Crystal Technology
Researcher (PI) Jan Peter Felix Lagerwall
Host Institution (HI) UNIVERSITE DU LUXEMBOURG
Call Details Consolidator Grant (CoG), PE8, ERC-2014-CoG
Summary A grand challenge in today’s materials research is the realization of flexible materials that are also intelligent and functional. They will be the enablers of true breakthroughs in the hot trends of soft robotics and wearable technology. The standard approach to the latter is to decorate rubber sheets with electronic components, yielding two serious flaws: rubber is uncomfortable as it does not breath and solid state electronics will eventually fail as a garment is flexed and stretched when worn. While the softness of rubber is ideal it must be used in the form of textile fibers to provide breathability, and for long-term failure resistance we need intelligent components that are soft. A solution to this conundrum was recently presented by the PI with the concept of liquid crystal (LC) electrospinning. The extreme responsiveness of LCs is transferred to a non-woven textile by incorporating the LC in the fiber core, yielding a smart flexible mat with sensory function. Moreover, it consumes no power, providing a further advantage over electronics-based approaches. In a second research line he uses microfluidics to make LC rubber microshells, functioning as autonomous actuators which may serve as innovative components for soft robotics, and photonic crystal shells. This interdisciplinary project presents an ambitious agenda to advance these new concepts to the realization of soft, stretchable intelligent materials of revolutionary character. Five specific objectives are in focus: 1) develop understanding of the dynamic response of LCs in these unconventional configurations; 2) establish interaction dynamics during polymerisation of an LC precursor; 3) elucidate LC response to gas exposure; 4) establish correlation between actuation response and internal order of curved LCE rubbers; and 5) assess usefulness of LC-functionalized fibers and polymerized LC shells, tubes and Janus particles in wearable sensors, soft robotic actuators and high-security identification tags.
Summary
A grand challenge in today’s materials research is the realization of flexible materials that are also intelligent and functional. They will be the enablers of true breakthroughs in the hot trends of soft robotics and wearable technology. The standard approach to the latter is to decorate rubber sheets with electronic components, yielding two serious flaws: rubber is uncomfortable as it does not breath and solid state electronics will eventually fail as a garment is flexed and stretched when worn. While the softness of rubber is ideal it must be used in the form of textile fibers to provide breathability, and for long-term failure resistance we need intelligent components that are soft. A solution to this conundrum was recently presented by the PI with the concept of liquid crystal (LC) electrospinning. The extreme responsiveness of LCs is transferred to a non-woven textile by incorporating the LC in the fiber core, yielding a smart flexible mat with sensory function. Moreover, it consumes no power, providing a further advantage over electronics-based approaches. In a second research line he uses microfluidics to make LC rubber microshells, functioning as autonomous actuators which may serve as innovative components for soft robotics, and photonic crystal shells. This interdisciplinary project presents an ambitious agenda to advance these new concepts to the realization of soft, stretchable intelligent materials of revolutionary character. Five specific objectives are in focus: 1) develop understanding of the dynamic response of LCs in these unconventional configurations; 2) establish interaction dynamics during polymerisation of an LC precursor; 3) elucidate LC response to gas exposure; 4) establish correlation between actuation response and internal order of curved LCE rubbers; and 5) assess usefulness of LC-functionalized fibers and polymerized LC shells, tubes and Janus particles in wearable sensors, soft robotic actuators and high-security identification tags.
Max ERC Funding
1 929 976 €
Duration
Start date: 2015-04-01, End date: 2020-03-31
Project acronym LIPA
Project A unified theory of finite-state recognisability
Researcher (PI) Mikolaj Konstanty Bojanczyk
Host Institution (HI) UNIWERSYTET WARSZAWSKI
Call Details Consolidator Grant (CoG), PE6, ERC-2015-CoG
Summary Finite-state devices like finite automata and monoids on finite words, or extensions to trees and infinite objects, are fundamental tools of logic in computer science. There are tens of models in the literature, ranging from finite automata on finite words to weighted automata on infinite trees. Many existing finite-state models share important similarities, like existence of canonical (minimal) devices, or decidability of emptiness, or a logic-automata connection. The first and primary goal of this project is to systematically investigate these similarities, and create a unified theory of finite-state devices, which:
1. covers the whole spectrum of existing finite-state devices, including settings with diverse inputs (e.g. words and trees, or infinite inputs, or infinite alphabets) and diverse outputs (e.g. Boolean like in the classical automata, or numbers like in weighted automata); and
2. sheds light on the correct notion of finite-state device in settings where there is no universally accepted choice or where finite-state devices have not been considered at all.
The theory of finite-state devices is one of those fields of theory where even the more advanced results have natural potential for applications. It is surprising and sad how little of this potential is normally realised, with most existing software using only the most rudimentary theoretical techniques. The second goal of the project is to create two tools which use more advanced aspects of the theory of automata to solve simple problems of wide applicability (i.e. at least tens of thousands of users):
1. a system that automatically grades exercises in automata, which goes beyond simple testing, and forces the students to write proofs
2. a system that uses learning to synthesise text transformations (such a search-and-replace, but also more powerful ones) by using examples
Summary
Finite-state devices like finite automata and monoids on finite words, or extensions to trees and infinite objects, are fundamental tools of logic in computer science. There are tens of models in the literature, ranging from finite automata on finite words to weighted automata on infinite trees. Many existing finite-state models share important similarities, like existence of canonical (minimal) devices, or decidability of emptiness, or a logic-automata connection. The first and primary goal of this project is to systematically investigate these similarities, and create a unified theory of finite-state devices, which:
1. covers the whole spectrum of existing finite-state devices, including settings with diverse inputs (e.g. words and trees, or infinite inputs, or infinite alphabets) and diverse outputs (e.g. Boolean like in the classical automata, or numbers like in weighted automata); and
2. sheds light on the correct notion of finite-state device in settings where there is no universally accepted choice or where finite-state devices have not been considered at all.
The theory of finite-state devices is one of those fields of theory where even the more advanced results have natural potential for applications. It is surprising and sad how little of this potential is normally realised, with most existing software using only the most rudimentary theoretical techniques. The second goal of the project is to create two tools which use more advanced aspects of the theory of automata to solve simple problems of wide applicability (i.e. at least tens of thousands of users):
1. a system that automatically grades exercises in automata, which goes beyond simple testing, and forces the students to write proofs
2. a system that uses learning to synthesise text transformations (such a search-and-replace, but also more powerful ones) by using examples
Max ERC Funding
1 768 125 €
Duration
Start date: 2016-05-01, End date: 2021-04-30
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 RealTCut
Project Towards real time multiscale simulation of cutting in non-linear materials
with applications to surgical simulation and computer guided surgery
Researcher (PI) Stéphane Pierre Alain Bordas
Host Institution (HI) UNIVERSITE DU LUXEMBOURG
Call Details Starting Grant (StG), PE8, ERC-2011-StG_20101014
Summary "Surgeons are trained as apprentices. Some conditions are rarely encountered and surgeons will only be trained in the specific skills associated with a given situation if they come across it. At the end of their residency, it is hoped that they will have faced sufficiently many cases to be competent. This can be dangerous to the patients.
If we were able to reproduce faithfully, in a virtual environment, the audio, visual and haptic experience of a surgeon as they prod, pull and incise tissue, then, surgeons would not have to train on cadavers, phantoms, or on the patients themselves.
Only a few researchers in the Computational Mechanics community have attacked the mechanical problems related to surgical simulation, so that mechanical faithfulness is not on par with audiovisual. This lack of fidelity in the reproduction of surgical acts such as cutting may explain why most surgeons who tested existing simulators report that the ""sensation"" fed back to them remains unrealistic. To date, the proposers are not aware of Computational Mechanics solutions addressing, at the same time, geometrical faithfulness, material realism, evolving cuts and quality control of the solution.
The measurable objectives for this research are as follows:
O1:Significantly alleviate the mesh generation and regeneration burden to represent organs’ geometries, underlying tissue microstructure and cuts with sufficient accuracy but minimal user intervention
O2:Move away from simplistic coarse-scale material models by deducing tissue rupture at the organ level from constitutive (e.g. damage) and contact models designed at the meso and micro scales
O3:Ensure real-time results through model order reduction coupled with the multi-scale fracture tools of O2
O4:Control solution accuracy and validate against a range of biomechanics problems including real-life brain surgery interventions with the available at our collaborators’"
Summary
"Surgeons are trained as apprentices. Some conditions are rarely encountered and surgeons will only be trained in the specific skills associated with a given situation if they come across it. At the end of their residency, it is hoped that they will have faced sufficiently many cases to be competent. This can be dangerous to the patients.
If we were able to reproduce faithfully, in a virtual environment, the audio, visual and haptic experience of a surgeon as they prod, pull and incise tissue, then, surgeons would not have to train on cadavers, phantoms, or on the patients themselves.
Only a few researchers in the Computational Mechanics community have attacked the mechanical problems related to surgical simulation, so that mechanical faithfulness is not on par with audiovisual. This lack of fidelity in the reproduction of surgical acts such as cutting may explain why most surgeons who tested existing simulators report that the ""sensation"" fed back to them remains unrealistic. To date, the proposers are not aware of Computational Mechanics solutions addressing, at the same time, geometrical faithfulness, material realism, evolving cuts and quality control of the solution.
The measurable objectives for this research are as follows:
O1:Significantly alleviate the mesh generation and regeneration burden to represent organs’ geometries, underlying tissue microstructure and cuts with sufficient accuracy but minimal user intervention
O2:Move away from simplistic coarse-scale material models by deducing tissue rupture at the organ level from constitutive (e.g. damage) and contact models designed at the meso and micro scales
O3:Ensure real-time results through model order reduction coupled with the multi-scale fracture tools of O2
O4:Control solution accuracy and validate against a range of biomechanics problems including real-life brain surgery interventions with the available at our collaborators’"
Max ERC Funding
1 343 955 €
Duration
Start date: 2012-01-01, End date: 2016-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
