Project acronym AGINGSEXDIFF
Project Aging Differently: Understanding Sex Differences in Reproductive, Demographic and Functional Senescence
Researcher (PI) Alexei Maklakov
Host Institution (HI) Uppsala University
Call Details Starting Grant (StG), LS8, ERC-2010-StG_20091118
Summary Sex differences in life span and aging are ubiquitous across the animal kingdom and represent a
long-standing challenge in evolutionary biology. In most species, including humans, sexes differ not
only in how long they live and when they start to senesce, but also in how they react to
environmental interventions aimed at prolonging their life span or decelerating the onset of aging.
Therefore, sex differences in life span and aging have important implications beyond the questions
posed by fundamental science. Both evolutionary reasons and medical implications of sex
differences in demographic, reproductive and physiological senescence are and will be crucial
targets of present and future research in the biology of aging. Here I propose a two-step approach
that can provide a significant breakthrough in our understanding of the biological basis of sex
differences in aging. First, I propose to resolve the age-old conundrum regarding the role of sexspecific
mortality rate in sex differences in aging by developing a series of targeted experimental
evolution studies in a novel model organism – the nematode, Caenorhabditis remanei. Second, I
address the role of intra-locus sexual conflict in the evolution of aging by combining novel
methodology from nutritional ecology – the Geometric Framework – with artificial selection
approach using the cricket Teleogryllus commodus and the fruitfly Drosophila melanogaster. I will
directly test the hypothesis that intra-locus sexual conflict mediates aging by restricting the
adaptive evolution of diet choice. By combining techniques from evolutionary biology and
nutritional ecology, this proposal will raise EU’s profile in integrative research, and contribute to
the training of young scientists in this rapidly developing field.
Summary
Sex differences in life span and aging are ubiquitous across the animal kingdom and represent a
long-standing challenge in evolutionary biology. In most species, including humans, sexes differ not
only in how long they live and when they start to senesce, but also in how they react to
environmental interventions aimed at prolonging their life span or decelerating the onset of aging.
Therefore, sex differences in life span and aging have important implications beyond the questions
posed by fundamental science. Both evolutionary reasons and medical implications of sex
differences in demographic, reproductive and physiological senescence are and will be crucial
targets of present and future research in the biology of aging. Here I propose a two-step approach
that can provide a significant breakthrough in our understanding of the biological basis of sex
differences in aging. First, I propose to resolve the age-old conundrum regarding the role of sexspecific
mortality rate in sex differences in aging by developing a series of targeted experimental
evolution studies in a novel model organism – the nematode, Caenorhabditis remanei. Second, I
address the role of intra-locus sexual conflict in the evolution of aging by combining novel
methodology from nutritional ecology – the Geometric Framework – with artificial selection
approach using the cricket Teleogryllus commodus and the fruitfly Drosophila melanogaster. I will
directly test the hypothesis that intra-locus sexual conflict mediates aging by restricting the
adaptive evolution of diet choice. By combining techniques from evolutionary biology and
nutritional ecology, this proposal will raise EU’s profile in integrative research, and contribute to
the training of young scientists in this rapidly developing field.
Max ERC Funding
1 391 904 €
Duration
Start date: 2010-12-01, End date: 2016-05-31
Project acronym AVIAN DIMORPHISM
Project The genomic and transcriptomic locus of sex-specific selection in birds
Researcher (PI) Judith Elizabeth Mank
Host Institution (HI) UNIVERSITY COLLEGE LONDON
Call Details Starting Grant (StG), LS8, ERC-2010-StG_20091118
Summary It has long been understood that genes contribute to phenotypes that are then the basis of selection. However, the nature and process of this relationship remains largely theoretical, and the relative contribution of change in gene expression and coding sequence to phenotypic diversification is unclear. The aim of this proposal is to fuse information about sexually dimorphic phenotypes, the mating systems and sexually antagonistic selective agents that shape sexual dimorphism, and the sex-biased gene expression patterns that encode sexual dimorphisms, in order to create a cohesive integrated understanding of the relationship between evolution, the genome, and the animal form. The primary approach of this project is to harnesses emergent DNA sequencing technologies in order to measure evolutionary change in gene expression and coding sequence in response to different sex-specific selection regimes in a clade of birds with divergent mating systems. Sex-specific selection pressures arise in large part as a consequence of mating system, however males and females share nearly identical genomes, especially in the vertebrates where the sex chromosomes house very small proportions of the overall transcriptome. This single shared genome creates sex-specific phenotypes via different gene expression levels in females and males, and these sex-biased genes connect sexual dimorphisms, and the sexually antagonistic selection pressures that shape them, with the regions of the genome that encode them.
The Galloanserae (fowl and waterfowl) will be used to in the proposed project, as this clade combines the necessary requirements of both variation in mating systems and a well-conserved reference genome (chicken). The study species selected from within the Galloanserae for the proposal exhibit a range of sexual dimorphism and sperm competition, and this will be exploited with next generation (454 and Illumina) genomic and transcriptomic data to study the gene expression patterns that underlie sexual dimorphisms, and the evolutionary pressures acting on them. This work will be complemented by the development of mathematical models of sex-specific evolution that will be tested against the gene expression and gene sequence data in order to understand the mechanisms by which sex-specific selection regimes, arising largely from mating systems, shape the phenotype via the genome.
Summary
It has long been understood that genes contribute to phenotypes that are then the basis of selection. However, the nature and process of this relationship remains largely theoretical, and the relative contribution of change in gene expression and coding sequence to phenotypic diversification is unclear. The aim of this proposal is to fuse information about sexually dimorphic phenotypes, the mating systems and sexually antagonistic selective agents that shape sexual dimorphism, and the sex-biased gene expression patterns that encode sexual dimorphisms, in order to create a cohesive integrated understanding of the relationship between evolution, the genome, and the animal form. The primary approach of this project is to harnesses emergent DNA sequencing technologies in order to measure evolutionary change in gene expression and coding sequence in response to different sex-specific selection regimes in a clade of birds with divergent mating systems. Sex-specific selection pressures arise in large part as a consequence of mating system, however males and females share nearly identical genomes, especially in the vertebrates where the sex chromosomes house very small proportions of the overall transcriptome. This single shared genome creates sex-specific phenotypes via different gene expression levels in females and males, and these sex-biased genes connect sexual dimorphisms, and the sexually antagonistic selection pressures that shape them, with the regions of the genome that encode them.
The Galloanserae (fowl and waterfowl) will be used to in the proposed project, as this clade combines the necessary requirements of both variation in mating systems and a well-conserved reference genome (chicken). The study species selected from within the Galloanserae for the proposal exhibit a range of sexual dimorphism and sperm competition, and this will be exploited with next generation (454 and Illumina) genomic and transcriptomic data to study the gene expression patterns that underlie sexual dimorphisms, and the evolutionary pressures acting on them. This work will be complemented by the development of mathematical models of sex-specific evolution that will be tested against the gene expression and gene sequence data in order to understand the mechanisms by which sex-specific selection regimes, arising largely from mating systems, shape the phenotype via the genome.
Max ERC Funding
1 350 804 €
Duration
Start date: 2011-01-01, End date: 2016-07-31
Project acronym BIG_IDEA
Project Building an Integrated Genetic Infectious Disease Epidemiology Approach
Researcher (PI) Francois Balloux
Host Institution (HI) UNIVERSITY COLLEGE LONDON
Call Details Starting Grant (StG), LS8, ERC-2010-StG_20091118
Summary Epidemiology and public health planning will increasingly rely on the analysis of genetic sequence data. The recent swine-derived influenza A/H1N1 pandemic may represent a tipping point in this trend, as it is arguably the first time when multiple strains of a human pathogen have been sequenced essentially in real time from the very beginning of its spread. However, the full potential of genetic information cannot be fully exploited to infer the spread of epidemics due to the lack of statistical methodologies capable of reconstructing transmission routes from genetic data structured both in time and space. To address this urgent need, we propose to develop a methodological framework for the reconstruction of the spatiotemporal dynamics of disease outbreaks and epidemics based on genetic sequence data. Rather than reconstructing most recent common ancestors as in phylogenetics, we will directly infer the most likely ancestries among the sampled isolates. This represents an entirely novel paradigm and allows for the development of statistically coherent and powerful inference software within a Bayesian framework. The methodological framework will be developed in parallel with the analysis of real genetic/genomic data from important human pathogens. We will in particular focus on the 2009 A/H1N1 pandemic influenza, methicilin-resistant Staphylococcus aureus clones (MRSAs), Batrachochytrium dendrobatidis, a fungus currently devastating amphibian populations worldwide. The tools we are proposing to develop are likely to impact radically on the field of infectious disease epidemiology and affect the way infectious emerging pathogens are monitored by biologists and public health professionals.
Summary
Epidemiology and public health planning will increasingly rely on the analysis of genetic sequence data. The recent swine-derived influenza A/H1N1 pandemic may represent a tipping point in this trend, as it is arguably the first time when multiple strains of a human pathogen have been sequenced essentially in real time from the very beginning of its spread. However, the full potential of genetic information cannot be fully exploited to infer the spread of epidemics due to the lack of statistical methodologies capable of reconstructing transmission routes from genetic data structured both in time and space. To address this urgent need, we propose to develop a methodological framework for the reconstruction of the spatiotemporal dynamics of disease outbreaks and epidemics based on genetic sequence data. Rather than reconstructing most recent common ancestors as in phylogenetics, we will directly infer the most likely ancestries among the sampled isolates. This represents an entirely novel paradigm and allows for the development of statistically coherent and powerful inference software within a Bayesian framework. The methodological framework will be developed in parallel with the analysis of real genetic/genomic data from important human pathogens. We will in particular focus on the 2009 A/H1N1 pandemic influenza, methicilin-resistant Staphylococcus aureus clones (MRSAs), Batrachochytrium dendrobatidis, a fungus currently devastating amphibian populations worldwide. The tools we are proposing to develop are likely to impact radically on the field of infectious disease epidemiology and affect the way infectious emerging pathogens are monitored by biologists and public health professionals.
Max ERC Funding
1 483 080 €
Duration
Start date: 2010-11-01, End date: 2015-10-31
Project acronym BLUELEAF
Project The adaptive advantages, evolution and development of iridescence in leaves
Researcher (PI) Heather Whitney
Host Institution (HI) UNIVERSITY OF BRISTOL
Call Details Starting Grant (StG), LS8, ERC-2010-StG_20091118
Summary Iridescence is a form of structural colour which changes hue according to the angle from which it is viewed. Blue iridescence caused by multilayers has been described on the leaves of taxonomically diverse species such as the lycophyte Selaginella uncinata and the angiosperm Begonia pavonina. While much is known about the role of leaf pigment colour, the adaptive role of leaf iridescence is unknown. Hypotheses have been put forward including 1) iridescence acts as disruptive camouflage against herbivores 2) it enhances light sensing and capture in low light conditions 3) it is a photoprotective mechanism to protect shade-adapted plants against high light levels. These hypotheses are not mutually exclusive: each function may be of varying importance in different environments. To understand any one function, we need a interdisciplinary approach considering all three potential functions and their interactions. The objective of my research would be to test these hypotheses, using animal behavioural and plant physiological methods, to determine the functions of leaf iridescence and how the plant has adapted to the reflection of developmentally vital wavelengths. Use of molecular and bioinformatics methods will elucidate the genes that control the production of this potentially multifunctional optical phenomenon. This research will provide a pioneering study into the generation, developmental impact and adaptive significance of iridescence in leaves. It would also answer questions at the frontiers of several fields including those of plant evolution, insect vision, methods of camouflage, the generation and role of animal iridescence, and could also potentially inspire synthetic biomimetic applications.
Summary
Iridescence is a form of structural colour which changes hue according to the angle from which it is viewed. Blue iridescence caused by multilayers has been described on the leaves of taxonomically diverse species such as the lycophyte Selaginella uncinata and the angiosperm Begonia pavonina. While much is known about the role of leaf pigment colour, the adaptive role of leaf iridescence is unknown. Hypotheses have been put forward including 1) iridescence acts as disruptive camouflage against herbivores 2) it enhances light sensing and capture in low light conditions 3) it is a photoprotective mechanism to protect shade-adapted plants against high light levels. These hypotheses are not mutually exclusive: each function may be of varying importance in different environments. To understand any one function, we need a interdisciplinary approach considering all three potential functions and their interactions. The objective of my research would be to test these hypotheses, using animal behavioural and plant physiological methods, to determine the functions of leaf iridescence and how the plant has adapted to the reflection of developmentally vital wavelengths. Use of molecular and bioinformatics methods will elucidate the genes that control the production of this potentially multifunctional optical phenomenon. This research will provide a pioneering study into the generation, developmental impact and adaptive significance of iridescence in leaves. It would also answer questions at the frontiers of several fields including those of plant evolution, insect vision, methods of camouflage, the generation and role of animal iridescence, and could also potentially inspire synthetic biomimetic applications.
Max ERC Funding
1 118 378 €
Duration
Start date: 2011-01-01, End date: 2016-07-31
Project acronym CAC
Project Cryptography and Complexity
Researcher (PI) Yuval Ishai
Host Institution (HI) TECHNION - ISRAEL INSTITUTE OF TECHNOLOGY
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary Modern cryptography has deeply rooted connections with computational complexity theory and other areas of computer science. This proposal suggests to explore several {\em new connections} between questions in cryptography and questions from other domains, including computational complexity, coding theory, and even the natural sciences. The project is expected to broaden the impact of ideas from cryptography on other domains, and on the other hand to benefit cryptography by applying tools from other domains towards better solutions for central problems in cryptography.
Summary
Modern cryptography has deeply rooted connections with computational complexity theory and other areas of computer science. This proposal suggests to explore several {\em new connections} between questions in cryptography and questions from other domains, including computational complexity, coding theory, and even the natural sciences. The project is expected to broaden the impact of ideas from cryptography on other domains, and on the other hand to benefit cryptography by applying tools from other domains towards better solutions for central problems in cryptography.
Max ERC Funding
1 459 703 €
Duration
Start date: 2010-12-01, End date: 2015-11-30
Project acronym CODAMODA
Project Controlling Data Movement in the Digital Age
Researcher (PI) Aggelos Kiayias
Host Institution (HI) ETHNIKO KAI KAPODISTRIAKO PANEPISTIMIO ATHINON
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary Nowadays human intellectual product is increasingly produced and disseminated solely in digital form. The capability of digital data for effortless reproduction and transfer has lead to a true revolution that impacts every aspect of human creativity. Nevertheless, as with every technological revolution, this digital media revolution comes with a dark side that, if left unaddressed, it will limit its impact and may counter its potential advantages. In particular, the way we produce and disseminate digital content today does not lend itself to controlling the way data move and change. It turns out that the power of being digital can be a double-edged sword: the ease of production, dissemination and editing also implies the ease of misappropriation, plagiarism and improper modification.
To counter the above problems, the proposed research activity will focus on the development of a new generation of enabling cryptographic technologies that have the power to facilitate the appropriate controls for data movement. Using the techniques developed in this project it will be feasible to build digital content distribution systems where content producers will have the full possible control on the dissemination of their intellectual product, while at the same time the rights of the end-users in terms of privacy and fair use can be preserved. The PI is uniquely qualified to carry out the proposed research activity as he has extensive prior experience in making innovations in the area of digital content distribution as well as in the management of research projects. As part of the project activities, the PI will establish the CODAMODA laboratory in the University of Athens and will seek opportunities for technology transfer and interdisciplinary work with the legal science community.
Summary
Nowadays human intellectual product is increasingly produced and disseminated solely in digital form. The capability of digital data for effortless reproduction and transfer has lead to a true revolution that impacts every aspect of human creativity. Nevertheless, as with every technological revolution, this digital media revolution comes with a dark side that, if left unaddressed, it will limit its impact and may counter its potential advantages. In particular, the way we produce and disseminate digital content today does not lend itself to controlling the way data move and change. It turns out that the power of being digital can be a double-edged sword: the ease of production, dissemination and editing also implies the ease of misappropriation, plagiarism and improper modification.
To counter the above problems, the proposed research activity will focus on the development of a new generation of enabling cryptographic technologies that have the power to facilitate the appropriate controls for data movement. Using the techniques developed in this project it will be feasible to build digital content distribution systems where content producers will have the full possible control on the dissemination of their intellectual product, while at the same time the rights of the end-users in terms of privacy and fair use can be preserved. The PI is uniquely qualified to carry out the proposed research activity as he has extensive prior experience in making innovations in the area of digital content distribution as well as in the management of research projects. As part of the project activities, the PI will establish the CODAMODA laboratory in the University of Athens and will seek opportunities for technology transfer and interdisciplinary work with the legal science community.
Max ERC Funding
1 212 960 €
Duration
Start date: 2011-04-01, End date: 2017-03-31
Project acronym COMPCAMERAANALYZ
Project Understanding Designing and Analyzing Computational Cameras
Researcher (PI) Anat Levin
Host Institution (HI) WEIZMANN INSTITUTE OF SCIENCE
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary Computational cameras go beyond 2D images and allow the extraction of more dimensions from the visual world such as depth, multiple viewpoints and multiple illumination conditions. They also allow us to overcome some of the traditional photography challenges such as defocus blur, motion blur, noise and resolution. The increasing variety of computational cameras is raising the need for a meaningful comparison across camera types. We would like to understand which cameras are better for specific tasks, which aspects of a camera make it better than others and what is the best performance we can hope to achieve.
Our 2008 paper introduced a general framework to address the design and analysis of computational cameras. A camera is modeled as a linear projection in ray space. Decoding the camera data then deals with inverting the linear projection. Since the number of sensor measurements is usually much smaller than the number of rays, the inversion must be treated as a Bayesian inference problem accounting for prior knowledge on the world.
Despite significant progress which has been made in the recent years, the space of computational cameras is still far from being understood.
Computational camera analysis raises the following research challenges: 1) What is a good way to model prior knowledge on ray space? 2) Seeking efficient inference algorithms and robust ways to decode the world from the camera measurements. 3) Evaluating the expected reconstruction accuracy of a given camera. 4) Using the expected reconstruction performance for evaluating and comparing camera types. 5) What is the best camera? Can we derive upper bounds on the optimal performance?
We propose research on all aspects of computational camera design and analysis. We propose new prior models which will significantly simplify the inference and evaluation tasks. We also propose new ways to bound and evaluate computational cameras with existing priors.
Summary
Computational cameras go beyond 2D images and allow the extraction of more dimensions from the visual world such as depth, multiple viewpoints and multiple illumination conditions. They also allow us to overcome some of the traditional photography challenges such as defocus blur, motion blur, noise and resolution. The increasing variety of computational cameras is raising the need for a meaningful comparison across camera types. We would like to understand which cameras are better for specific tasks, which aspects of a camera make it better than others and what is the best performance we can hope to achieve.
Our 2008 paper introduced a general framework to address the design and analysis of computational cameras. A camera is modeled as a linear projection in ray space. Decoding the camera data then deals with inverting the linear projection. Since the number of sensor measurements is usually much smaller than the number of rays, the inversion must be treated as a Bayesian inference problem accounting for prior knowledge on the world.
Despite significant progress which has been made in the recent years, the space of computational cameras is still far from being understood.
Computational camera analysis raises the following research challenges: 1) What is a good way to model prior knowledge on ray space? 2) Seeking efficient inference algorithms and robust ways to decode the world from the camera measurements. 3) Evaluating the expected reconstruction accuracy of a given camera. 4) Using the expected reconstruction performance for evaluating and comparing camera types. 5) What is the best camera? Can we derive upper bounds on the optimal performance?
We propose research on all aspects of computational camera design and analysis. We propose new prior models which will significantly simplify the inference and evaluation tasks. We also propose new ways to bound and evaluate computational cameras with existing priors.
Max ERC Funding
756 845 €
Duration
Start date: 2010-12-01, End date: 2015-11-30
Project acronym COSYM
Project Computational Symmetry for Geometric Data Analysis and Design
Researcher (PI) Mark Pauly
Host Institution (HI) ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary The analysis and synthesis of complex 3D geometric data sets is of crucial importance in many scientific disciplines (e.g. bio-medicine, material science, mechanical engineering, physics) and industrial applications (e.g. drug design, entertainment, architecture). We are currently witnessing a tremendous increase in the size and complexity of geometric data, largely fueled by significant advances in 3D acquisition and digital production technology. However, existing computational tools are often not suited to handle this complexity.
The goal of this project is to explore a fundamentally different way of processing 3D geometry. We will investigate a new generalized model of geometric symmetry as a unifying concept for studying spatial organization in geometric data. This model allows exposing the inherent redundancies in digital 3D data and will enable truly scalable algorithms for analysis, processing, and design of large-scale geometric data sets. The proposed research will address a number of fundamental questions: What is the information content of 3D geometric models? How can we represent, store, and transmit geometric data most efficiently? Can we we use symmetry to repair deficiencies and reduce noise in acquired data? What is the role of symmetry in the design process and how can it be used to reduce complexity?
I will investigate these questions with an integrated approach that combines thorough theoretical studies with practical solutions for real-world applications.
The proposed research has a strong interdisciplinary component and will consider the same fundamental questions from different perspectives, closely interacting with scientists of various disciplines, as well artists, architects, and designers.
Summary
The analysis and synthesis of complex 3D geometric data sets is of crucial importance in many scientific disciplines (e.g. bio-medicine, material science, mechanical engineering, physics) and industrial applications (e.g. drug design, entertainment, architecture). We are currently witnessing a tremendous increase in the size and complexity of geometric data, largely fueled by significant advances in 3D acquisition and digital production technology. However, existing computational tools are often not suited to handle this complexity.
The goal of this project is to explore a fundamentally different way of processing 3D geometry. We will investigate a new generalized model of geometric symmetry as a unifying concept for studying spatial organization in geometric data. This model allows exposing the inherent redundancies in digital 3D data and will enable truly scalable algorithms for analysis, processing, and design of large-scale geometric data sets. The proposed research will address a number of fundamental questions: What is the information content of 3D geometric models? How can we represent, store, and transmit geometric data most efficiently? Can we we use symmetry to repair deficiencies and reduce noise in acquired data? What is the role of symmetry in the design process and how can it be used to reduce complexity?
I will investigate these questions with an integrated approach that combines thorough theoretical studies with practical solutions for real-world applications.
The proposed research has a strong interdisciplinary component and will consider the same fundamental questions from different perspectives, closely interacting with scientists of various disciplines, as well artists, architects, and designers.
Max ERC Funding
1 160 302 €
Duration
Start date: 2011-02-01, End date: 2016-01-31
Project acronym CRYSP
Project CRYSP: A Novel Framework for Collaboratively Building Cryptographically Secure Programs and their Proofs
Researcher (PI) Karthikeyan Bhargavan
Host Institution (HI) INSTITUT NATIONAL DE RECHERCHE ENINFORMATIQUE ET AUTOMATIQUE
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary The field of software security analysis stands at a critical juncture.
Applications have become too large for security experts to examine by hand,
automated verification tools do not scale, and the risks of deploying insecure software are too great to tolerate anything less than mathematical proof.
A radical shift of strategy is needed if programming and analysis techniques are to keep up in a networked world where increasing amounts of governmental and individual information are generated, manipulated, and accessed through web-based software applications.
The basic tenet of this proposal is that the main roadblock to the security verification of a large program is not its size, but rather the lack of precise security specifications for the underlying libraries and security-critical application code. Since, large-scale software is often a collaborative effort, no single programmer knows all the design goals. Hence, this proposal advocates a collaborative specification and verification framework that helps teams of programmers write detailed security specifications incrementally and then verify that they are satisfied by the source program.
The main scientific challenge is to develop new program verification techniques that can be applied collaboratively, incrementally, and modularly to application and library code written in mainstream programming languages. The validation of this approach will be through substantial case studies. Our aim is to produce the first verified open source cryptographic protocol library and the first web applications with formal proofs of security.
The proposed project is bold and ambitious, but it is certainly feasible, and has the potential to change how software security is analyzed for years to come.
Summary
The field of software security analysis stands at a critical juncture.
Applications have become too large for security experts to examine by hand,
automated verification tools do not scale, and the risks of deploying insecure software are too great to tolerate anything less than mathematical proof.
A radical shift of strategy is needed if programming and analysis techniques are to keep up in a networked world where increasing amounts of governmental and individual information are generated, manipulated, and accessed through web-based software applications.
The basic tenet of this proposal is that the main roadblock to the security verification of a large program is not its size, but rather the lack of precise security specifications for the underlying libraries and security-critical application code. Since, large-scale software is often a collaborative effort, no single programmer knows all the design goals. Hence, this proposal advocates a collaborative specification and verification framework that helps teams of programmers write detailed security specifications incrementally and then verify that they are satisfied by the source program.
The main scientific challenge is to develop new program verification techniques that can be applied collaboratively, incrementally, and modularly to application and library code written in mainstream programming languages. The validation of this approach will be through substantial case studies. Our aim is to produce the first verified open source cryptographic protocol library and the first web applications with formal proofs of security.
The proposed project is bold and ambitious, but it is certainly feasible, and has the potential to change how software security is analyzed for years to come.
Max ERC Funding
1 406 726 €
Duration
Start date: 2010-11-01, End date: 2015-10-31
Project acronym CSP-COMPLEXITY
Project Constraint Satisfaction Problems: Algorithms and Complexity
Researcher (PI) Manuel Bodirsky
Host Institution (HI) TECHNISCHE UNIVERSITAET DRESDEN
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary The complexity of Constraint Satisfaction Problems (CSPs) has become a major common research focus of graph theory, artificial intelligence, and finite model theory. A recently discovered connection between the complexity of CSPs on finite domains to central problems in universal algebra led to additional activity in the area.
The goal of this project is to extend the powerful techniques for constraint satisfaction to CSPs with infinite domains. The generalization of CSPs to infinite domains enhances dramatically the range of computational problems that can be analyzed with tools from constraint satisfaction complexity. Many problems from areas that have so far seen no interaction with constraint satisfaction complexity theory can be formulated using infinite domains (and not with finite domains), e.g. in phylogenetic reconstruction, temporal and spatial reasoning, computer algebra, and operations research. It turns out that the search for systematic complexity classification in infinite domain constraint satisfaction often leads to fundamental algorithmic results.
The generalization of constraint satisfaction to infinite domains poses several mathematical challenges: To make the universal algebraic approach work for infinite domain constraint satisfaction we need fundamental concepts from model theory. Luckily, the new mathematical challenges come together with additional strong tools, such as Ramsey theory or results from model theory. The most important challgenges are of an algorithmic nature: finding efficient algorithms for significant constraint languages, but also finding natural classes of problems that can be solved by a given algorithm.
Summary
The complexity of Constraint Satisfaction Problems (CSPs) has become a major common research focus of graph theory, artificial intelligence, and finite model theory. A recently discovered connection between the complexity of CSPs on finite domains to central problems in universal algebra led to additional activity in the area.
The goal of this project is to extend the powerful techniques for constraint satisfaction to CSPs with infinite domains. The generalization of CSPs to infinite domains enhances dramatically the range of computational problems that can be analyzed with tools from constraint satisfaction complexity. Many problems from areas that have so far seen no interaction with constraint satisfaction complexity theory can be formulated using infinite domains (and not with finite domains), e.g. in phylogenetic reconstruction, temporal and spatial reasoning, computer algebra, and operations research. It turns out that the search for systematic complexity classification in infinite domain constraint satisfaction often leads to fundamental algorithmic results.
The generalization of constraint satisfaction to infinite domains poses several mathematical challenges: To make the universal algebraic approach work for infinite domain constraint satisfaction we need fundamental concepts from model theory. Luckily, the new mathematical challenges come together with additional strong tools, such as Ramsey theory or results from model theory. The most important challgenges are of an algorithmic nature: finding efficient algorithms for significant constraint languages, but also finding natural classes of problems that can be solved by a given algorithm.
Max ERC Funding
830 316 €
Duration
Start date: 2011-01-01, End date: 2015-12-31