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 Load Slice Core
Project Load Slice Core: A Power and Cost-Efficient Microarchitecture for the Future
Researcher (PI) Lieven Eeckhout
Host Institution (HI) UNIVERSITEIT GENT
Call Details Advanced Grant (AdG), PE6, ERC-2016-ADG
Summary The ideal processor building block is a power and cost-efficient core that can maximize the extraction of memory hierarchy parallelism, a combination that neither traditional in-order nor out-of-order cores provide. We propose the Load Slice Core microarchitecture, a restricted out-of-order engine aimed squarely at extracting memory hierarchy parallelism, which, according to preliminary results, delivers a nearly 8 times higher performance per Watt per euro compared to an out-of-order core.
The overarching objective of this project to fully determine the potential of the Load Slice Core as a key building block for a novel multi-core processor architecture needed in light of both current and future challenges in software and hardware, including variable thread-level parallelism, managed language workloads, the importance of sequential performance, and the quest for significantly improved power and cost efficiency.
We anticipate significant improvement in multi-core performance within the available power budget and cost by combining chip-level dynamism to cope with variable thread-level parallelism along with the inherent power- and cost-efficient Load Slice Core design. If we are able to demonstrate the true value and potential of the Load Slice Core to address future hardware and software challenges, this project will have a long-lasting impact on the microprocessor industry moving forward.
Summary
The ideal processor building block is a power and cost-efficient core that can maximize the extraction of memory hierarchy parallelism, a combination that neither traditional in-order nor out-of-order cores provide. We propose the Load Slice Core microarchitecture, a restricted out-of-order engine aimed squarely at extracting memory hierarchy parallelism, which, according to preliminary results, delivers a nearly 8 times higher performance per Watt per euro compared to an out-of-order core.
The overarching objective of this project to fully determine the potential of the Load Slice Core as a key building block for a novel multi-core processor architecture needed in light of both current and future challenges in software and hardware, including variable thread-level parallelism, managed language workloads, the importance of sequential performance, and the quest for significantly improved power and cost efficiency.
We anticipate significant improvement in multi-core performance within the available power budget and cost by combining chip-level dynamism to cope with variable thread-level parallelism along with the inherent power- and cost-efficient Load Slice Core design. If we are able to demonstrate the true value and potential of the Load Slice Core to address future hardware and software challenges, this project will have a long-lasting impact on the microprocessor industry moving forward.
Max ERC Funding
2 499 500 €
Duration
Start date: 2018-01-01, End date: 2022-12-31
Project acronym Re-SENSE
Project RESOURCE-EFFICIENT SENSING THROUGH DYNAMIC ATTENTION-SCALABILITY
Researcher (PI) Marian Kristien VERHELST
Host Institution (HI) KATHOLIEKE UNIVERSITEIT LEUVEN
Call Details Starting Grant (StG), PE6, ERC-2016-STG
Summary It is hard to stand on one leg if we close our eyes. We have trouble tasting food without smelling. And when we talk with other people, we observe their lips to understand them better. We, humans, are masters in sensor fusion as we can seamlessly combine information coming from different senses to improve our judgements. Intriguingly, in order to fuse information efficiently, we do not always devote the same level of attention or mental effort to each of the many sensory streams available to us. This dynamic attention-scalability allows us to always extract the maximum amount of relevant information under our limited human computational bandwidth.
Would it not be great if electronics had the same capabilities? While many devices are nowadays equipped with a massive amount of sensors, they typically cannot effectively fuse more than a few of them. The rigid way in which sensory data is combined results in large computational workloads, preventing effective multi-sensor fusion in resource-constrained applications such as robotics, wearables, biomedical monitoring or user interfacing.
The Re-SENSE project will bring attention-scalable sensing to resource-scarce devices, which are constrained in terms of energy, throughput, latency or memory resources. This is achieved by jointly:
1) Developing resource-aware inference and fusion algorithms, which maximize information capture in function of hardware resource usage, dynamically tuning sensory attention levels
2) Implementing dynamic, wide-range resource-scalable inference processors, allowing to exploit this attention-scalability for drastically improved efficiency
The attention-scalable sensing concept will be demonstrated in 2 highly resource-constrained applications: a) latency-critical cell sorting and b) energy-critical epilepsy monitoring.
This combination of processor design, reconfigurable hardware and embedded machine learning fits perfectly to the PI’s expertise gained at Intel Labs, UC Berkeley and KULeuven.
Summary
It is hard to stand on one leg if we close our eyes. We have trouble tasting food without smelling. And when we talk with other people, we observe their lips to understand them better. We, humans, are masters in sensor fusion as we can seamlessly combine information coming from different senses to improve our judgements. Intriguingly, in order to fuse information efficiently, we do not always devote the same level of attention or mental effort to each of the many sensory streams available to us. This dynamic attention-scalability allows us to always extract the maximum amount of relevant information under our limited human computational bandwidth.
Would it not be great if electronics had the same capabilities? While many devices are nowadays equipped with a massive amount of sensors, they typically cannot effectively fuse more than a few of them. The rigid way in which sensory data is combined results in large computational workloads, preventing effective multi-sensor fusion in resource-constrained applications such as robotics, wearables, biomedical monitoring or user interfacing.
The Re-SENSE project will bring attention-scalable sensing to resource-scarce devices, which are constrained in terms of energy, throughput, latency or memory resources. This is achieved by jointly:
1) Developing resource-aware inference and fusion algorithms, which maximize information capture in function of hardware resource usage, dynamically tuning sensory attention levels
2) Implementing dynamic, wide-range resource-scalable inference processors, allowing to exploit this attention-scalability for drastically improved efficiency
The attention-scalable sensing concept will be demonstrated in 2 highly resource-constrained applications: a) latency-critical cell sorting and b) energy-critical epilepsy monitoring.
This combination of processor design, reconfigurable hardware and embedded machine learning fits perfectly to the PI’s expertise gained at Intel Labs, UC Berkeley and KULeuven.
Max ERC Funding
1 484 562 €
Duration
Start date: 2017-03-01, End date: 2022-02-28
Project acronym SWORD
Project Security Without Obscurity for Reliable Devices
Researcher (PI) FRANCOIS-XAVIER LESLIE A STANDAERT
Host Institution (HI) UNIVERSITE CATHOLIQUE DE LOUVAIN
Call Details Consolidator Grant (CoG), PE6, ERC-2016-COG
Summary Cryptographic implementations are traditionally evaluated based on a trade-off between security and efficiency. However, when it comes to physical security against attacks exploiting side-channel leakages or fault insertions, this approach is limited by the difficulty to define the adversaries (e.g. their knowledge about the target implementation) and to specify sound physical assumptions. Quite naturally, the problem becomes even more challenging in contexts where implementations can be maliciously modified during design or fabrication via so-called hardware Trojans. To a large extent, these vulnerabilities echo the general challenge of restoring trust that is faced by cryptographic research in view of the recent Snowden revelations. In this context, we believe that the design of small components able to perform secure computations locally will be an important building block of future information systems. For this purpose, the SWORD project envisions a paradigm shift in embedded security, by adding trust as an essential element in the evaluation of physically secure objects. Our two main ingredients to reach this ambitious goal are a good separation between mathematics and physics, and improved transparency in security evaluations. That is, we want cryptographic implementations to rely on physical assumptions that can be empirically verified, in order to obtain sound security guarantees based on mathematical proofs or arguments. And we want to make the empirical verification of physical assumptions more transparent, by considering open source hardware and software. By allowing adversaries and evaluators to know implementation details, we expect to enable a better understanding of the fundamentals of physical security, therefore leading to improved security, efficiency and trust in the longer term. That is, we hope to establish security guarantees based on a good understanding of the physics, rather than the (relative) misunderstanding caused by closed systems.
Summary
Cryptographic implementations are traditionally evaluated based on a trade-off between security and efficiency. However, when it comes to physical security against attacks exploiting side-channel leakages or fault insertions, this approach is limited by the difficulty to define the adversaries (e.g. their knowledge about the target implementation) and to specify sound physical assumptions. Quite naturally, the problem becomes even more challenging in contexts where implementations can be maliciously modified during design or fabrication via so-called hardware Trojans. To a large extent, these vulnerabilities echo the general challenge of restoring trust that is faced by cryptographic research in view of the recent Snowden revelations. In this context, we believe that the design of small components able to perform secure computations locally will be an important building block of future information systems. For this purpose, the SWORD project envisions a paradigm shift in embedded security, by adding trust as an essential element in the evaluation of physically secure objects. Our two main ingredients to reach this ambitious goal are a good separation between mathematics and physics, and improved transparency in security evaluations. That is, we want cryptographic implementations to rely on physical assumptions that can be empirically verified, in order to obtain sound security guarantees based on mathematical proofs or arguments. And we want to make the empirical verification of physical assumptions more transparent, by considering open source hardware and software. By allowing adversaries and evaluators to know implementation details, we expect to enable a better understanding of the fundamentals of physical security, therefore leading to improved security, efficiency and trust in the longer term. That is, we hope to establish security guarantees based on a good understanding of the physics, rather than the (relative) misunderstanding caused by closed systems.
Max ERC Funding
1 997 661 €
Duration
Start date: 2017-09-01, End date: 2022-08-31
