Project acronym COMPMUSIC
Project Computational models for the discovery of the world's music
Researcher (PI) Francesc Xavier Serra Casals
Host Institution (HI) UNIVERSIDAD POMPEU FABRA
Call Details Advanced Grant (AdG), PE6, ERC-2010-AdG_20100224
Summary Current IT research does not respond to the world's multi-cultural reality. It could be argued that we are imposing the paradigms of our market-driven western culture also on IT and that current IT research results will only facilitate the access of a small part of the world’s information to a small part of the world's population. Most IT research is being carried out with a western centred approach and as a result, our data models, cognition models, user models, interaction models, ontologies, … are all culturally biased. This fact is quite evident in music information research, since, despite the world's richness in musical cultures, most of the research is centred on CDs and metadata of our western commercial music. CompMusic wants to break this huge research bias. By approaching musical information modelling from a multicultural perspective it aims at advancing our state of the art while facilitating the discovery and reuse of the music produced outside the western commercial context. But the development of computational models to address the world’s music information richness cannot be done from the West looking out; we have to involve researchers and musical experts immersed in the different cultures. Their contribution is fundamental to develop the appropriate multicultural musicological and cognitive frameworks from which we should then carry our research on finding appropriate musical features, ontologies, data representations, user interfaces and user centred approaches. CompMusic will investigate some of the most consolidated non-western classical music traditions, Indian (hindustani, carnatic), Turkish-Arab (ottoman, andalusian), and Chinese (han), developing the needed computational models to bring their music into the current globalized information framework. Using these music cultures as case studies, cultures that are alive and have a strong influence in current society, we can develop rich information models that can take advantage of the existing information coming from musicological and cultural studies, from mature performance practice traditions and from active social contexts. With this approach we aim at challenging the current western centred information paradigms, advance our IT research, and contribute to our rich multicultural society.
Summary
Current IT research does not respond to the world's multi-cultural reality. It could be argued that we are imposing the paradigms of our market-driven western culture also on IT and that current IT research results will only facilitate the access of a small part of the world’s information to a small part of the world's population. Most IT research is being carried out with a western centred approach and as a result, our data models, cognition models, user models, interaction models, ontologies, … are all culturally biased. This fact is quite evident in music information research, since, despite the world's richness in musical cultures, most of the research is centred on CDs and metadata of our western commercial music. CompMusic wants to break this huge research bias. By approaching musical information modelling from a multicultural perspective it aims at advancing our state of the art while facilitating the discovery and reuse of the music produced outside the western commercial context. But the development of computational models to address the world’s music information richness cannot be done from the West looking out; we have to involve researchers and musical experts immersed in the different cultures. Their contribution is fundamental to develop the appropriate multicultural musicological and cognitive frameworks from which we should then carry our research on finding appropriate musical features, ontologies, data representations, user interfaces and user centred approaches. CompMusic will investigate some of the most consolidated non-western classical music traditions, Indian (hindustani, carnatic), Turkish-Arab (ottoman, andalusian), and Chinese (han), developing the needed computational models to bring their music into the current globalized information framework. Using these music cultures as case studies, cultures that are alive and have a strong influence in current society, we can develop rich information models that can take advantage of the existing information coming from musicological and cultural studies, from mature performance practice traditions and from active social contexts. With this approach we aim at challenging the current western centred information paradigms, advance our IT research, and contribute to our rich multicultural society.
Max ERC Funding
2 443 200 €
Duration
Start date: 2011-07-01, End date: 2017-06-30
Project acronym COMPUSAPIEN
Project Computing Server Architecture with Joint Power and Cooling Integration at the Nanoscale
Researcher (PI) David ATIENZA ALONSO
Host Institution (HI) ECOLE POLYTECHNIQUE FEDERALE DE LAUSANNE
Call Details Consolidator Grant (CoG), PE6, ERC-2016-COG
Summary The soaring demand for computing power in the last years has grown faster than semiconductor technology evolution can sustain, and has produced as collateral undesirable effect a surge in power consumption and heat density in computing servers. Although computing servers are the foundations of the digital revolution, their current designs require 30-40% of the energy supplied to be dissipated in cooling. The remaining energy is used for computation, but their complex many-core designs produce very high operating temperatures. Thus, operating all the cores continuously at maximum performance levels results in system overheating and failures. This situation is limiting the benefits of technology scaling.
The COMPUSAPIEN proposal aims to completely revise the current computing server architecture. In particular, inspired by the mammalian brain, this proposal targets to design a disruptive three-dimensional (3D) computing server architecture that overcomes the prevailing worst-case power and cooling provisioning paradigm for servers. This new 3D server design champions a heterogeneous many-core architecture template with an integrated on-chip microfluidic fuel cell network for joint cooling delivery and power supply. Also, it will include a novel predictive controller based on holistic power-temperature models, which exploit the server software stack to achieve energy-scalable computing capabilities. Because of its integrated electronic-electrochemical architecture design, COMPUSAPIEN is clearly a high-risk high-reward proposal that will bring drastic energy savings with respect to current server design approaches, and will guarantee energy scalability in future server architectures. To realize this vision, COMPUSAPIEN will develop and integrate breakthrough innovations in heterogeneous computing architectures, cooling-power subsystem design, combined microfluidic power delivery and temperature management in computers.
Summary
The soaring demand for computing power in the last years has grown faster than semiconductor technology evolution can sustain, and has produced as collateral undesirable effect a surge in power consumption and heat density in computing servers. Although computing servers are the foundations of the digital revolution, their current designs require 30-40% of the energy supplied to be dissipated in cooling. The remaining energy is used for computation, but their complex many-core designs produce very high operating temperatures. Thus, operating all the cores continuously at maximum performance levels results in system overheating and failures. This situation is limiting the benefits of technology scaling.
The COMPUSAPIEN proposal aims to completely revise the current computing server architecture. In particular, inspired by the mammalian brain, this proposal targets to design a disruptive three-dimensional (3D) computing server architecture that overcomes the prevailing worst-case power and cooling provisioning paradigm for servers. This new 3D server design champions a heterogeneous many-core architecture template with an integrated on-chip microfluidic fuel cell network for joint cooling delivery and power supply. Also, it will include a novel predictive controller based on holistic power-temperature models, which exploit the server software stack to achieve energy-scalable computing capabilities. Because of its integrated electronic-electrochemical architecture design, COMPUSAPIEN is clearly a high-risk high-reward proposal that will bring drastic energy savings with respect to current server design approaches, and will guarantee energy scalability in future server architectures. To realize this vision, COMPUSAPIEN will develop and integrate breakthrough innovations in heterogeneous computing architectures, cooling-power subsystem design, combined microfluidic power delivery and temperature management in computers.
Max ERC Funding
1 999 281 €
Duration
Start date: 2017-06-01, End date: 2022-05-31
Project acronym COMPUTED
Project Computational User Interface Design
Researcher (PI) Antti Olavi Oulasvirta
Host Institution (HI) AALTO KORKEAKOULUSAATIO SR
Call Details Starting Grant (StG), PE6, ERC-2014-STG
Summary PROBLEM: Despite extensive research on human-computer interaction (HCI), no method exists that guarantees the optimal or even a provably good user interface (UI) design. The prevailing approach relies on heuristics and iteration, which can be costly and even ineffective, because UI design often involves combinatorially hard problems with immense design spaces, multiple objectives and constraints, and complex user behavior.
OBJECTIVES: COMPUTED establishes the foundations for optimizing UI designs. A design can be automatically optimized to given objectives and constraints by using combinatorial optimization methods that deploy predictive models of user behavior as objective functions. Although previous work has shown some improvements to usability, the scope has been restricted to keyboards and widgets. COMPUTED researches methods that can vastly expand the scope of optimizable problems. First, algorithmic support is developed for acquiring objective functions that cover the main human factors in a given HCI task. Second, formal analysis of decision problems in UI design allows combating a broader range of design tasks with efficient and appropriate optimization methods. Third, a novel interactive UI optimization paradigm for UI designers promotes fast convergence to good results even in the face of uncertainty and incomplete knowledge.
IMPACT: Combinatorial UI optimization offers a strong complement to the prevailing design approaches. Because the structured search process has a high chance of finding good solutions, optimization could improve the quality of interfaces used in everyday life. Optimization can also increase cost-efficiency, because reference to optimality can eliminate fruitless iteration. Moreover, because no preknowledge of UI design is required, even novices will be able to design great UIs. Even in “messy,” less well-defined problems, it may support designers by allowing them to delegate the solving of well-known sub-problems.
Summary
PROBLEM: Despite extensive research on human-computer interaction (HCI), no method exists that guarantees the optimal or even a provably good user interface (UI) design. The prevailing approach relies on heuristics and iteration, which can be costly and even ineffective, because UI design often involves combinatorially hard problems with immense design spaces, multiple objectives and constraints, and complex user behavior.
OBJECTIVES: COMPUTED establishes the foundations for optimizing UI designs. A design can be automatically optimized to given objectives and constraints by using combinatorial optimization methods that deploy predictive models of user behavior as objective functions. Although previous work has shown some improvements to usability, the scope has been restricted to keyboards and widgets. COMPUTED researches methods that can vastly expand the scope of optimizable problems. First, algorithmic support is developed for acquiring objective functions that cover the main human factors in a given HCI task. Second, formal analysis of decision problems in UI design allows combating a broader range of design tasks with efficient and appropriate optimization methods. Third, a novel interactive UI optimization paradigm for UI designers promotes fast convergence to good results even in the face of uncertainty and incomplete knowledge.
IMPACT: Combinatorial UI optimization offers a strong complement to the prevailing design approaches. Because the structured search process has a high chance of finding good solutions, optimization could improve the quality of interfaces used in everyday life. Optimization can also increase cost-efficiency, because reference to optimality can eliminate fruitless iteration. Moreover, because no preknowledge of UI design is required, even novices will be able to design great UIs. Even in “messy,” less well-defined problems, it may support designers by allowing them to delegate the solving of well-known sub-problems.
Max ERC Funding
1 499 790 €
Duration
Start date: 2015-04-01, End date: 2020-03-31
Project acronym Con Espressione
Project Getting at the Heart of Things: Towards Expressivity-aware Computer Systems in Music
Researcher (PI) Gerhard Widmer
Host Institution (HI) UNIVERSITAT LINZ
Call Details Advanced Grant (AdG), PE6, ERC-2014-ADG
Summary What makes music so important, what can make a performance so special and stirring? It is the things the music expresses, the emotions it induces, the associations it evokes, the drama and characters it portrays. The sources of this expressivity are manifold: the music itself, its structure, orchestration, personal associations, social settings, but also – and very importantly – the act of performance, the interpretation and expressive intentions made explicit by the musicians through nuances in timing, dynamics etc.
Thanks to research in fields like Music Information Research (MIR), computers can do many useful things with music, from beat and rhythm detection to song identification and tracking. However, they are still far from grasping the essence of music: they cannot tell whether a performance expresses playfulness or ennui, solemnity or gaiety, determination or uncertainty; they cannot produce music with a desired expressive quality; they cannot interact with human musicians in a truly musical way, recognising and responding to the expressive intentions implied in their playing.
The project is about developing machines that are aware of certain dimensions of expressivity, specifically in the domain of (classical) music, where expressivity is both essential and – at least as far as it relates to the act of performance – can be traced back to well-defined and measurable parametric dimensions (such as timing, dynamics, articulation). We will develop systems that can recognise, characterise, search music by expressive aspects, generate, modify, and react to expressive qualities in music. To do so, we will (1) bring together the fields of AI, Machine Learning, MIR and Music Performance Research; (2) integrate theories from Musicology to build more well-founded models of music understanding; (3) support model learning and validation with massive musical corpora of a size and quality unprecedented in computational music research.
Summary
What makes music so important, what can make a performance so special and stirring? It is the things the music expresses, the emotions it induces, the associations it evokes, the drama and characters it portrays. The sources of this expressivity are manifold: the music itself, its structure, orchestration, personal associations, social settings, but also – and very importantly – the act of performance, the interpretation and expressive intentions made explicit by the musicians through nuances in timing, dynamics etc.
Thanks to research in fields like Music Information Research (MIR), computers can do many useful things with music, from beat and rhythm detection to song identification and tracking. However, they are still far from grasping the essence of music: they cannot tell whether a performance expresses playfulness or ennui, solemnity or gaiety, determination or uncertainty; they cannot produce music with a desired expressive quality; they cannot interact with human musicians in a truly musical way, recognising and responding to the expressive intentions implied in their playing.
The project is about developing machines that are aware of certain dimensions of expressivity, specifically in the domain of (classical) music, where expressivity is both essential and – at least as far as it relates to the act of performance – can be traced back to well-defined and measurable parametric dimensions (such as timing, dynamics, articulation). We will develop systems that can recognise, characterise, search music by expressive aspects, generate, modify, and react to expressive qualities in music. To do so, we will (1) bring together the fields of AI, Machine Learning, MIR and Music Performance Research; (2) integrate theories from Musicology to build more well-founded models of music understanding; (3) support model learning and validation with massive musical corpora of a size and quality unprecedented in computational music research.
Max ERC Funding
2 318 750 €
Duration
Start date: 2016-01-01, End date: 2020-12-31
Project acronym CONVEXVISION
Project Convex Optimization Methods for Computer Vision and Image Analysis
Researcher (PI) Daniel Cremers
Host Institution (HI) TECHNISCHE UNIVERSITAET MUENCHEN
Call Details Starting Grant (StG), PE6, ERC-2009-StG
Summary Optimization methods have become an established paradigm to address most Computer Vision challenges including the
reconstruction of three-dimensional objects from multiple images, or the tracking of a deformable shape over time. Yet, it has
been largely overlooked that optimization approaches are practically useless if they do not come with efficient algorithms to
compute minimizers of respective energies. Most existing formulations give rise to non-convex energies. As a consequence,
solutions highly depend on the choice of minimization scheme and implementational (initialization, time step sizes, etc.), with
little or no guarantees regarding the quality of computed solutions and their robustness to perturbations of the input data.
In the proposed research project, we plan to develop optimization methods for Computer Vision which allow to efficiently
compute globally optimal solutions. Preliminary results indicate that this will drastically leverage the power of optimization
methods and their applicability in a substantially broader context. Specifically we will focus on three lines of research: 1) We
will develop convex formulations for a variety of challenges. While convex formulations are currently being developed for
low-level problems such as image segmentation, our main effort will focus on carrying convex optimization to higher level
problems of image understanding and scene interpretation. 2) We will investigate alternative strategies of global optimization
by means of discrete graph theoretic methods. We will characterize advantages and drawbacks of continuous and discrete
methods and thereby develop novel algorithms combining the advantages of both approaches. 3) We will go beyond convex
formulations, developing relaxation schemes that compute near-optimal solutions for problems that cannot be expressed by
convex functionals.
Summary
Optimization methods have become an established paradigm to address most Computer Vision challenges including the
reconstruction of three-dimensional objects from multiple images, or the tracking of a deformable shape over time. Yet, it has
been largely overlooked that optimization approaches are practically useless if they do not come with efficient algorithms to
compute minimizers of respective energies. Most existing formulations give rise to non-convex energies. As a consequence,
solutions highly depend on the choice of minimization scheme and implementational (initialization, time step sizes, etc.), with
little or no guarantees regarding the quality of computed solutions and their robustness to perturbations of the input data.
In the proposed research project, we plan to develop optimization methods for Computer Vision which allow to efficiently
compute globally optimal solutions. Preliminary results indicate that this will drastically leverage the power of optimization
methods and their applicability in a substantially broader context. Specifically we will focus on three lines of research: 1) We
will develop convex formulations for a variety of challenges. While convex formulations are currently being developed for
low-level problems such as image segmentation, our main effort will focus on carrying convex optimization to higher level
problems of image understanding and scene interpretation. 2) We will investigate alternative strategies of global optimization
by means of discrete graph theoretic methods. We will characterize advantages and drawbacks of continuous and discrete
methods and thereby develop novel algorithms combining the advantages of both approaches. 3) We will go beyond convex
formulations, developing relaxation schemes that compute near-optimal solutions for problems that cannot be expressed by
convex functionals.
Max ERC Funding
1 985 400 €
Duration
Start date: 2010-09-01, End date: 2015-08-31
Project acronym CoPS
Project Coevolutionary Policy Search
Researcher (PI) Shimon Azariah Whiteson
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Starting Grant (StG), PE6, ERC-2014-STG
Summary I propose to develop a new class of decision-theoretic planning methods that overcome fundamental obstacles to the efficient optimization of autonomous agents. Creating agents that are effective in diverse settings is a key goal of artificial intelligence with enormous potential implications: robotic agents would be invaluable in homes, factories, and high-risk settings; software agents could revolutionize e-commerce, information retrieval, and traffic control.
The main challenge lies in specifying an agent's policy: the behavioral strategy that determines its actions. Since the complexity of realistic tasks makes manual policy construction hopeless, there is great demand for decision-theoretic planning methods that automatically discover good policies. Despite enormous progress, the grand challenge of efficiently discovering effective policies for complex tasks remains unmet.
A fundamental obstacle is the cost of policy evaluation: estimating a policy's quality by averaging performance over multiple trials. This cost grows quickly with increases in task complexity (making trials more expensive) or stochasticity (necessitating more trials).
To address this difficulty, I propose a new approach that simultaneously optimizes both policies and the manner in which those policies are evaluated. The key insight is that, in many tasks, many trials are wasted because they do not elicit the controllable rare events critical for distinguishing between policies. Thus, I will develop methods that leverage coevolution to automatically discover the best events, instead of sampling them randomly.
If successful, this project will greatly improve the efficiency of decision-theoretic planning and, in turn, help realize the potential of autonomous agents. In addition, by automatically identifying the most useful events, the resulting methods will help isolate critical factors in performance and thus yield new insights into what makes decision-theoretic problems hard.
Summary
I propose to develop a new class of decision-theoretic planning methods that overcome fundamental obstacles to the efficient optimization of autonomous agents. Creating agents that are effective in diverse settings is a key goal of artificial intelligence with enormous potential implications: robotic agents would be invaluable in homes, factories, and high-risk settings; software agents could revolutionize e-commerce, information retrieval, and traffic control.
The main challenge lies in specifying an agent's policy: the behavioral strategy that determines its actions. Since the complexity of realistic tasks makes manual policy construction hopeless, there is great demand for decision-theoretic planning methods that automatically discover good policies. Despite enormous progress, the grand challenge of efficiently discovering effective policies for complex tasks remains unmet.
A fundamental obstacle is the cost of policy evaluation: estimating a policy's quality by averaging performance over multiple trials. This cost grows quickly with increases in task complexity (making trials more expensive) or stochasticity (necessitating more trials).
To address this difficulty, I propose a new approach that simultaneously optimizes both policies and the manner in which those policies are evaluated. The key insight is that, in many tasks, many trials are wasted because they do not elicit the controllable rare events critical for distinguishing between policies. Thus, I will develop methods that leverage coevolution to automatically discover the best events, instead of sampling them randomly.
If successful, this project will greatly improve the efficiency of decision-theoretic planning and, in turn, help realize the potential of autonomous agents. In addition, by automatically identifying the most useful events, the resulting methods will help isolate critical factors in performance and thus yield new insights into what makes decision-theoretic problems hard.
Max ERC Funding
1 480 632 €
Duration
Start date: 2015-10-01, End date: 2020-09-30
Project acronym CoqHoTT
Project Coq for Homotopy Type Theory
Researcher (PI) nicolas Tabareau
Host Institution (HI) INSTITUT NATIONAL DE RECHERCHE ENINFORMATIQUE ET AUTOMATIQUE
Call Details Starting Grant (StG), PE6, ERC-2014-STG
Summary Every year, software bugs cost hundreds of millions of euros to companies and administrations. Hence, software quality is a prevalent notion and interactive theorem provers based on type theory have shown their efficiency to prove correctness of important pieces of software like the C compiler of the CompCert project. One main interest of such theorem provers is the ability to extract directly the code from the proof. Unfortunately, their democratization suffers from a major drawback, the mismatch between equality in mathematics and in type theory. Thus, significant Coq developments have only been done by virtuosos playing with advanced concepts of computer science and mathematics. Recently, an extension of type theory with homotopical concepts such as univalence is gaining traction because it allows for the first time to marry together expected principles of equality. But the univalence principle has been treated so far as a new axiom which breaks one fundamental property of mechanized proofs: the ability to compute with programs that make use of this axiom. The main goal of the CoqHoTT project is to provide a new generation of proof assistants with a computational version of univalence and use them as a base to implement effective logical model transformation so that the power of the internal logic of the proof assistant needed to prove the correctness of a program can be decided and changed at compile time—according to a trade-off between efficiency and logical expressivity. Our approach is based on a radically new compilation phase technique into a core type theory to modularize the difficulty of finding a decidable type checking algorithm for homotopy type theory.
The impact of the CoqHoTT project will be very strong. Even if Coq is already a success, this project will promote it as a major proof assistant, for both computer scientists and mathematicians. CoqHoTT will become an essential tool for program certification and formalization of mathematics.
Summary
Every year, software bugs cost hundreds of millions of euros to companies and administrations. Hence, software quality is a prevalent notion and interactive theorem provers based on type theory have shown their efficiency to prove correctness of important pieces of software like the C compiler of the CompCert project. One main interest of such theorem provers is the ability to extract directly the code from the proof. Unfortunately, their democratization suffers from a major drawback, the mismatch between equality in mathematics and in type theory. Thus, significant Coq developments have only been done by virtuosos playing with advanced concepts of computer science and mathematics. Recently, an extension of type theory with homotopical concepts such as univalence is gaining traction because it allows for the first time to marry together expected principles of equality. But the univalence principle has been treated so far as a new axiom which breaks one fundamental property of mechanized proofs: the ability to compute with programs that make use of this axiom. The main goal of the CoqHoTT project is to provide a new generation of proof assistants with a computational version of univalence and use them as a base to implement effective logical model transformation so that the power of the internal logic of the proof assistant needed to prove the correctness of a program can be decided and changed at compile time—according to a trade-off between efficiency and logical expressivity. Our approach is based on a radically new compilation phase technique into a core type theory to modularize the difficulty of finding a decidable type checking algorithm for homotopy type theory.
The impact of the CoqHoTT project will be very strong. Even if Coq is already a success, this project will promote it as a major proof assistant, for both computer scientists and mathematicians. CoqHoTT will become an essential tool for program certification and formalization of mathematics.
Max ERC Funding
1 498 290 €
Duration
Start date: 2015-06-01, End date: 2020-05-31
Project acronym CORNET
Project Provably Correct Networks
Researcher (PI) Costin RAICIU
Host Institution (HI) UNIVERSITATEA POLITEHNICA DIN BUCURESTI
Call Details Starting Grant (StG), PE6, ERC-2017-STG
Summary Networks are the backbone of our society, but configuring them is error-prone and tedious: misconfigured networks result in headline grabbing network outages that affect many users and hurt company revenues while security breaches that endanger millions of customers. There are currently no guarantees that deployed networks correctly implement their operator’s policy.
Existing research has focused on two directions: a) low level analysis and instrumentation of real networking code prevents memory bugs in individual network elements, but does not capture network-wide properties desired by operators such as reachability or loop freedom; b) high-level analysis of network-wide properties to verify operator policies on abstract network models; unfortunately, there are no guarantees that the models are an accurate representation of the real network code, and often low-level errors invalidate the conclusions of the high-level analysis.
We propose to achieve provably correct networks by simultaneously targeting both low-level security concerns and network-wide policy compliance checking. Our key proposal is to rely on exhaustive network symbolic execution for verification and to automatically generate provably correct implementations from network models. Generating efficient code that is equivalent to the model poses great challenges that we will address with three key contributions:
a) We will develop a novel theoretical equivalence framework based on symbolic execution semantics, as well as equivalence-preserving model transformations to automatically optimize network models for runtime efficiency.
b) We will develop compilers that take network models and generate functionally equivalent and efficient executable code for different targets (e.g. P4 and C).
c) We will design algorithms that generate and insert runtime guards that ensure correctness of the network with respect to the desired policy even when legacy boxes are deployed in the network.
Summary
Networks are the backbone of our society, but configuring them is error-prone and tedious: misconfigured networks result in headline grabbing network outages that affect many users and hurt company revenues while security breaches that endanger millions of customers. There are currently no guarantees that deployed networks correctly implement their operator’s policy.
Existing research has focused on two directions: a) low level analysis and instrumentation of real networking code prevents memory bugs in individual network elements, but does not capture network-wide properties desired by operators such as reachability or loop freedom; b) high-level analysis of network-wide properties to verify operator policies on abstract network models; unfortunately, there are no guarantees that the models are an accurate representation of the real network code, and often low-level errors invalidate the conclusions of the high-level analysis.
We propose to achieve provably correct networks by simultaneously targeting both low-level security concerns and network-wide policy compliance checking. Our key proposal is to rely on exhaustive network symbolic execution for verification and to automatically generate provably correct implementations from network models. Generating efficient code that is equivalent to the model poses great challenges that we will address with three key contributions:
a) We will develop a novel theoretical equivalence framework based on symbolic execution semantics, as well as equivalence-preserving model transformations to automatically optimize network models for runtime efficiency.
b) We will develop compilers that take network models and generate functionally equivalent and efficient executable code for different targets (e.g. P4 and C).
c) We will design algorithms that generate and insert runtime guards that ensure correctness of the network with respect to the desired policy even when legacy boxes are deployed in the network.
Max ERC Funding
1 325 000 €
Duration
Start date: 2018-01-01, End date: 2022-12-31
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 CoVeCe
Project Coinduction for Verification and Certification
Researcher (PI) Damien Gabriel Jacques Pous
Host Institution (HI) CENTRE NATIONAL DE LA RECHERCHE SCIENTIFIQUE CNRS
Call Details Starting Grant (StG), PE6, ERC-2015-STG
Summary Software and hardware bugs cost hundreds of millions of euros every year to companies and administrations. Formal methods like verification provide automatic means of finding some of these bugs. Certification, using proof assistants like Coq or Isabelle/HOL, make it possible to guarantee the absence of bugs (up to a certain point).
These two kinds of tools are crucial in order to design safer programs and machines. Unfortunately, state-of-the art tools are not yet satisfactory. Verification tools often face state-explosion problems and require more efficient algorithms; certification tools need more automation: they currently require too much time and expertise, even for basic tasks that could be handled easily through verification.
In recent work with Bonchi, we have shown that an extremely simple idea from concurrency theory could give rise to algorithms that are often exponentially faster than the algorithms currently used in verification tools.
My claim is that this idea could scale to richer models, revolutionising existing verification tools and providing algorithms for problems whose decidability is still open.
Moreover, the expected simplicity of those algorithms will make it possible to implement them inside certification tools such as Coq, to provide powerful automation techniques based on verification techniques. In the end, we will thus provide efficient and certified verification tools going beyond the state-of-the-art, but also the ability to use such tools inside the Coq proof assistant, to alleviate the cost of certification tasks.
Summary
Software and hardware bugs cost hundreds of millions of euros every year to companies and administrations. Formal methods like verification provide automatic means of finding some of these bugs. Certification, using proof assistants like Coq or Isabelle/HOL, make it possible to guarantee the absence of bugs (up to a certain point).
These two kinds of tools are crucial in order to design safer programs and machines. Unfortunately, state-of-the art tools are not yet satisfactory. Verification tools often face state-explosion problems and require more efficient algorithms; certification tools need more automation: they currently require too much time and expertise, even for basic tasks that could be handled easily through verification.
In recent work with Bonchi, we have shown that an extremely simple idea from concurrency theory could give rise to algorithms that are often exponentially faster than the algorithms currently used in verification tools.
My claim is that this idea could scale to richer models, revolutionising existing verification tools and providing algorithms for problems whose decidability is still open.
Moreover, the expected simplicity of those algorithms will make it possible to implement them inside certification tools such as Coq, to provide powerful automation techniques based on verification techniques. In the end, we will thus provide efficient and certified verification tools going beyond the state-of-the-art, but also the ability to use such tools inside the Coq proof assistant, to alleviate the cost of certification tasks.
Max ERC Funding
1 407 413 €
Duration
Start date: 2016-04-01, End date: 2021-03-31
