Project acronym ACCORD
Project Algorithms for Complex Collective Decisions on Structured Domains
Researcher (PI) Edith Elkind
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Starting Grant (StG), PE6, ERC-2014-STG
Summary Algorithms for Complex Collective Decisions on Structured Domains.
The aim of this proposal is to substantially advance the field of Computational Social Choice, by developing new tools and methodologies that can be used for making complex group decisions in rich and structured environments. We consider settings where each member of a decision-making body has preferences over a finite set of alternatives, and the goal is to synthesise a collective preference over these alternatives, which may take the form of a partial order over the set of alternatives with a predefined structure: examples include selecting a fixed-size set of alternatives, a ranking of the alternatives, a winner and up to two runner-ups, etc. We will formulate desiderata that apply to such preference aggregation procedures, design specific procedures that satisfy as many of these desiderata as possible, and develop efficient algorithms for computing them. As the latter step may be infeasible on general preference domains, we will focus on identifying the least restrictive domains that enable efficient computation, and use real-life preference data to verify whether the associated restrictions are likely to be satisfied in realistic preference aggregation scenarios. Also, we will determine whether our preference aggregation procedures are computationally resistant to malicious behavior. To lower the cognitive burden on the decision-makers, we will extend our procedures to accept partial rankings as inputs. Finally, to further contribute towards bridging the gap between theory and practice of collective decision making, we will provide open-source software implementations of our procedures, and reach out to the potential users to obtain feedback on their practical applicability.
Summary
Algorithms for Complex Collective Decisions on Structured Domains.
The aim of this proposal is to substantially advance the field of Computational Social Choice, by developing new tools and methodologies that can be used for making complex group decisions in rich and structured environments. We consider settings where each member of a decision-making body has preferences over a finite set of alternatives, and the goal is to synthesise a collective preference over these alternatives, which may take the form of a partial order over the set of alternatives with a predefined structure: examples include selecting a fixed-size set of alternatives, a ranking of the alternatives, a winner and up to two runner-ups, etc. We will formulate desiderata that apply to such preference aggregation procedures, design specific procedures that satisfy as many of these desiderata as possible, and develop efficient algorithms for computing them. As the latter step may be infeasible on general preference domains, we will focus on identifying the least restrictive domains that enable efficient computation, and use real-life preference data to verify whether the associated restrictions are likely to be satisfied in realistic preference aggregation scenarios. Also, we will determine whether our preference aggregation procedures are computationally resistant to malicious behavior. To lower the cognitive burden on the decision-makers, we will extend our procedures to accept partial rankings as inputs. Finally, to further contribute towards bridging the gap between theory and practice of collective decision making, we will provide open-source software implementations of our procedures, and reach out to the potential users to obtain feedback on their practical applicability.
Max ERC Funding
1 395 933 €
Duration
Start date: 2015-07-01, End date: 2020-06-30
Project acronym ACMO
Project Systematic dissection of molecular machines and neural circuits coordinating C. elegans aggregation behaviour
Researcher (PI) Mario De Bono
Host Institution (HI) MEDICAL RESEARCH COUNCIL
Call Details Advanced Grant (AdG), LS5, ERC-2010-AdG_20100317
Summary Elucidating how neural circuits coordinate behaviour, and how molecules underpin the properties of individual neurons are major goals of neuroscience. Optogenetics and neural imaging combined with the powerful genetics and well-described nervous system of C. elegans offer special opportunities to address these questions. Previously, we identified a series of sensory neurons that modulate aggregation of C. elegans. These include neurons that respond to O2, CO2, noxious cues, satiety state, and pheromones. We propose to take our analysis to the next level by dissecting how, in mechanistic molecular terms, these distributed inputs modify the activity of populations of interneurons and motoneurons to coordinate group formation. Our strategy is to develop new, highly parallel approaches to replace the traditional piecemeal analysis.
We propose to:
1) Harness next generation sequencing (NGS) to forward genetics, rapidly to identify a molecular ¿parts list¿ for aggregation. Much of the genetics has been done: we have identified almost 200 mutations that inhibit or enhance aggregation but otherwise show no overt phenotype. A pilot study of 50 of these mutations suggests they identify dozens of genes not previously implicated in aggregation. NGS will allow us to molecularly identify these genes in a few months, providing multiple entry points to study molecular and circuitry mechanisms for behaviour.
2) Develop new methods to image the activity of populations of neurons in immobilized and freely moving animals, using genetically encoded indicators such as the calcium sensor cameleon and the voltage indicator mermaid.
This will be the first time a complex behaviour has been dissected in this way. We expect to identify novel conserved molecular and circuitry mechanisms.
Summary
Elucidating how neural circuits coordinate behaviour, and how molecules underpin the properties of individual neurons are major goals of neuroscience. Optogenetics and neural imaging combined with the powerful genetics and well-described nervous system of C. elegans offer special opportunities to address these questions. Previously, we identified a series of sensory neurons that modulate aggregation of C. elegans. These include neurons that respond to O2, CO2, noxious cues, satiety state, and pheromones. We propose to take our analysis to the next level by dissecting how, in mechanistic molecular terms, these distributed inputs modify the activity of populations of interneurons and motoneurons to coordinate group formation. Our strategy is to develop new, highly parallel approaches to replace the traditional piecemeal analysis.
We propose to:
1) Harness next generation sequencing (NGS) to forward genetics, rapidly to identify a molecular ¿parts list¿ for aggregation. Much of the genetics has been done: we have identified almost 200 mutations that inhibit or enhance aggregation but otherwise show no overt phenotype. A pilot study of 50 of these mutations suggests they identify dozens of genes not previously implicated in aggregation. NGS will allow us to molecularly identify these genes in a few months, providing multiple entry points to study molecular and circuitry mechanisms for behaviour.
2) Develop new methods to image the activity of populations of neurons in immobilized and freely moving animals, using genetically encoded indicators such as the calcium sensor cameleon and the voltage indicator mermaid.
This will be the first time a complex behaviour has been dissected in this way. We expect to identify novel conserved molecular and circuitry mechanisms.
Max ERC Funding
2 439 996 €
Duration
Start date: 2011-04-01, End date: 2017-03-31
Project acronym ACrossWire
Project A Cross-Correlated Approach to Engineering Nitride Nanowires
Researcher (PI) Hannah Jane JOYCE
Host Institution (HI) THE CHANCELLOR MASTERS AND SCHOLARS OF THE UNIVERSITY OF CAMBRIDGE
Call Details Starting Grant (StG), PE7, ERC-2016-STG
Summary Nanowires based on group III–nitride semiconductors exhibit outstanding potential for emerging applications in energy-efficient lighting, optoelectronics and solar energy harvesting. Nitride nanowires, tailored at the nanoscale, should overcome many of the challenges facing conventional planar nitride materials, and also add extraordinary new functionality to these materials. However, progress towards III–nitride nanowire devices has been hampered by the challenges in quantifying nanowire electrical properties using conventional contact-based measurements. Without reliable electrical transport data, it is extremely difficult to optimise nanowire growth and device design. This project aims to overcome this problem through an unconventional approach: advanced contact-free electrical measurements. Contact-free measurements, growth studies, and device studies will be cross-correlated to provide unprecedented insight into the growth mechanisms that govern nanowire electronic properties and ultimately dictate device performance. A key contact-free technique at the heart of this proposal is ultrafast terahertz conductivity spectroscopy: an advanced technique ideal for probing nanowire electrical properties. We will develop new methods to enable the full suite of contact-free (including terahertz, photoluminescence and cathodoluminescence measurements) and contact-based measurements to be performed with high spatial resolution on the same nanowires. This will provide accurate, comprehensive and cross-correlated feedback to guide growth studies and expedite the targeted development of nanowires with specified functionality. We will apply this powerful approach to tailor nanowires as photoelectrodes for solar photoelectrochemical water splitting. This is an application for which nitride nanowires have outstanding, yet unfulfilled, potential. This project will thus harness the true potential of nitride nanowires and bring them to the forefront of 21st century technology.
Summary
Nanowires based on group III–nitride semiconductors exhibit outstanding potential for emerging applications in energy-efficient lighting, optoelectronics and solar energy harvesting. Nitride nanowires, tailored at the nanoscale, should overcome many of the challenges facing conventional planar nitride materials, and also add extraordinary new functionality to these materials. However, progress towards III–nitride nanowire devices has been hampered by the challenges in quantifying nanowire electrical properties using conventional contact-based measurements. Without reliable electrical transport data, it is extremely difficult to optimise nanowire growth and device design. This project aims to overcome this problem through an unconventional approach: advanced contact-free electrical measurements. Contact-free measurements, growth studies, and device studies will be cross-correlated to provide unprecedented insight into the growth mechanisms that govern nanowire electronic properties and ultimately dictate device performance. A key contact-free technique at the heart of this proposal is ultrafast terahertz conductivity spectroscopy: an advanced technique ideal for probing nanowire electrical properties. We will develop new methods to enable the full suite of contact-free (including terahertz, photoluminescence and cathodoluminescence measurements) and contact-based measurements to be performed with high spatial resolution on the same nanowires. This will provide accurate, comprehensive and cross-correlated feedback to guide growth studies and expedite the targeted development of nanowires with specified functionality. We will apply this powerful approach to tailor nanowires as photoelectrodes for solar photoelectrochemical water splitting. This is an application for which nitride nanowires have outstanding, yet unfulfilled, potential. This project will thus harness the true potential of nitride nanowires and bring them to the forefront of 21st century technology.
Max ERC Funding
1 499 195 €
Duration
Start date: 2017-04-01, End date: 2022-03-31
Project acronym ACTIVE_NEUROGENESIS
Project Activity-dependent signaling in radial glial cells and their neuronal progeny
Researcher (PI) Colin Akerman
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Starting Grant (StG), LS5, ERC-2009-StG
Summary A significant advance in the field of development has been the appreciation that radial glial cells are progenitors and give birth to neurons in the brain. In order to advance this exciting area of biology, we need approaches that combine structural and functional studies of these cells. This is reflected by the emerging realisation that dynamic interactions involving radial glia may be critical for the regulation of their proliferative behaviour. It has been observed that radial glia experience transient elevations in intracellular Ca2+ but the nature of these signals, and the information that they convey, is not known. The inability to observe these cells in vivo and over the course of their development has also meant that basic questions remain unexplored. For instance, how does the behaviour of a radial glial cell at one point in development, influence the final identity of its progeny? I propose to build a research team that will capitalise upon methods we have developed for observing individual radial glia and their progeny in an intact vertebrate nervous system. The visual system of Xenopus Laevis tadpoles offers non-invasive optical access to the brain, making time-lapse imaging of single cells feasible over minutes and weeks. The system s anatomy lends itself to techniques that measure the activity of the cells in a functional sensory network. We will use this to examine signalling mechanisms in radial glia and how a radial glial cell s experience influences its proliferative behaviour and the types of neuron it generates. We will also examine the interactions that continue between a radial glial cell and its daughter neurons. Finally, we will explore the relationships that exist within neuronal progeny derived from a single radial glial cell.
Summary
A significant advance in the field of development has been the appreciation that radial glial cells are progenitors and give birth to neurons in the brain. In order to advance this exciting area of biology, we need approaches that combine structural and functional studies of these cells. This is reflected by the emerging realisation that dynamic interactions involving radial glia may be critical for the regulation of their proliferative behaviour. It has been observed that radial glia experience transient elevations in intracellular Ca2+ but the nature of these signals, and the information that they convey, is not known. The inability to observe these cells in vivo and over the course of their development has also meant that basic questions remain unexplored. For instance, how does the behaviour of a radial glial cell at one point in development, influence the final identity of its progeny? I propose to build a research team that will capitalise upon methods we have developed for observing individual radial glia and their progeny in an intact vertebrate nervous system. The visual system of Xenopus Laevis tadpoles offers non-invasive optical access to the brain, making time-lapse imaging of single cells feasible over minutes and weeks. The system s anatomy lends itself to techniques that measure the activity of the cells in a functional sensory network. We will use this to examine signalling mechanisms in radial glia and how a radial glial cell s experience influences its proliferative behaviour and the types of neuron it generates. We will also examine the interactions that continue between a radial glial cell and its daughter neurons. Finally, we will explore the relationships that exist within neuronal progeny derived from a single radial glial cell.
Max ERC Funding
1 284 808 €
Duration
Start date: 2010-02-01, End date: 2015-01-31
Project acronym ACTSELECTCONTEXT
Project Action Selection under Contextual Uncertainty: the Role of Learning and Effective Connectivity in the Human Brain
Researcher (PI) Sven Bestmann
Host Institution (HI) UNIVERSITY COLLEGE LONDON
Call Details Starting Grant (StG), LS5, ERC-2010-StG_20091118
Summary In a changing world, one hallmark feature of human behaviour is the ability to learn about the statistics of the environment and use this prior information for action selection. Knowing about a forthcoming event allows for adjusting our actions pre-emptively, which can optimize survival.
This proposal studies how the human brain learns about the uncertainty in the environment, and how this leads to flexible and efficient action selection.
I hypothesise that the accumulation of evidence for future movements through learning reflects a fundamental organisational principle for action control. This explains widely distributed perceptual-, learning-, decision-, and movement-related signals in the human brain. However, little is known about the concerted interplay between brain regions in terms of effective connectivity which is required for flexible behaviour.
My proposal seeks to shed light on this unresolved issue. To this end, I will use i) a multi-disciplinary neuroimaging approach, together with model-based analyses and Bayesian model comparison, adapted to human reaching behaviour as occurring in daily life; and ii) two novel approaches for testing effective connectivity: dynamic causal modelling (DCM) and concurrent transcranial magnetic stimulation-functional magnetic resonance imaging.
My prediction is that action selection relies on effective connectivity changes, which are a function of the prior information that the brain has to learn about.
If true, this will provide novel insight into the human ability to select actions, based on learning about the uncertainty which is inherent in contextual information. This is relevant for understanding action selection during development and ageing, and for pathologies of action such as Parkinson s disease or stroke.
Summary
In a changing world, one hallmark feature of human behaviour is the ability to learn about the statistics of the environment and use this prior information for action selection. Knowing about a forthcoming event allows for adjusting our actions pre-emptively, which can optimize survival.
This proposal studies how the human brain learns about the uncertainty in the environment, and how this leads to flexible and efficient action selection.
I hypothesise that the accumulation of evidence for future movements through learning reflects a fundamental organisational principle for action control. This explains widely distributed perceptual-, learning-, decision-, and movement-related signals in the human brain. However, little is known about the concerted interplay between brain regions in terms of effective connectivity which is required for flexible behaviour.
My proposal seeks to shed light on this unresolved issue. To this end, I will use i) a multi-disciplinary neuroimaging approach, together with model-based analyses and Bayesian model comparison, adapted to human reaching behaviour as occurring in daily life; and ii) two novel approaches for testing effective connectivity: dynamic causal modelling (DCM) and concurrent transcranial magnetic stimulation-functional magnetic resonance imaging.
My prediction is that action selection relies on effective connectivity changes, which are a function of the prior information that the brain has to learn about.
If true, this will provide novel insight into the human ability to select actions, based on learning about the uncertainty which is inherent in contextual information. This is relevant for understanding action selection during development and ageing, and for pathologies of action such as Parkinson s disease or stroke.
Max ERC Funding
1 341 805 €
Duration
Start date: 2011-06-01, End date: 2016-05-31
Project acronym AdOMiS
Project Adaptive Optical Microscopy Systems: Unifying theory, practice and applications
Researcher (PI) Martin BOOTH
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Advanced Grant (AdG), PE7, ERC-2015-AdG
Summary Recent technological advances in optical microscopy have vastly broadened the possibilities for applications in the biomedical sciences. Fluorescence microscopy is the central tool for investigation of molecular structures and dynamics that take place in the cellular and tissue environment. Coupled with progress in labeling methods, these microscopes permit observation of biological structures and processes with unprecedented sensitivity and resolution. This work has been enabled by the engineering development of diverse optical systems that provide different capabilities for the imaging toolkit. All such methods rely upon high fidelity optics to provide optimal resolution and efficiency, but they all suffer from aberrations caused by refractive index variations within the specimen. It is widely accepted that in many applications this fundamental problem prevents optimum operation and limits capability. Adaptive optics (AO) has been introduced to overcome these limitations by correcting aberrations and a range of demonstrations has shown clearly its potential. Indeed, it shows great promise to improve virtually all types of research or commercial microscopes, but significant challenges must still be met before AO can be widely implemented in routine imaging. Current advances are being made through development of bespoke AO solutions to individual imaging tasks. However, the diversity of microscopy methods means that individual solutions are often not translatable to other systems. This proposal is directed towards the creation of theoretical and practical frameworks that tie together AO concepts and provide a suite of scientific tools with broad application. This will be achieved through a systems approach that encompasses theoretical modelling, optical engineering and the requirements of biological applications. Additional outputs will include practical designs, operating protocols and software algorithms that will support next generation AO microscope systems.
Summary
Recent technological advances in optical microscopy have vastly broadened the possibilities for applications in the biomedical sciences. Fluorescence microscopy is the central tool for investigation of molecular structures and dynamics that take place in the cellular and tissue environment. Coupled with progress in labeling methods, these microscopes permit observation of biological structures and processes with unprecedented sensitivity and resolution. This work has been enabled by the engineering development of diverse optical systems that provide different capabilities for the imaging toolkit. All such methods rely upon high fidelity optics to provide optimal resolution and efficiency, but they all suffer from aberrations caused by refractive index variations within the specimen. It is widely accepted that in many applications this fundamental problem prevents optimum operation and limits capability. Adaptive optics (AO) has been introduced to overcome these limitations by correcting aberrations and a range of demonstrations has shown clearly its potential. Indeed, it shows great promise to improve virtually all types of research or commercial microscopes, but significant challenges must still be met before AO can be widely implemented in routine imaging. Current advances are being made through development of bespoke AO solutions to individual imaging tasks. However, the diversity of microscopy methods means that individual solutions are often not translatable to other systems. This proposal is directed towards the creation of theoretical and practical frameworks that tie together AO concepts and provide a suite of scientific tools with broad application. This will be achieved through a systems approach that encompasses theoretical modelling, optical engineering and the requirements of biological applications. Additional outputs will include practical designs, operating protocols and software algorithms that will support next generation AO microscope systems.
Max ERC Funding
3 234 789 €
Duration
Start date: 2016-09-01, End date: 2021-08-31
Project acronym ALEXANDRIA
Project Large-Scale Formal Proof for the Working Mathematician
Researcher (PI) Lawrence PAULSON
Host Institution (HI) THE CHANCELLOR MASTERS AND SCHOLARS OF THE UNIVERSITY OF CAMBRIDGE
Call Details Advanced Grant (AdG), PE6, ERC-2016-ADG
Summary Mathematical proofs have always been prone to error. Today, proofs can be hundreds of pages long and combine results from many specialisms, making them almost impossible to check. One solution is to deploy modern verification technology. Interactive theorem provers have demonstrated their potential as vehicles for formalising mathematics through achievements such as the verification of the Kepler Conjecture. Proofs done using such tools reach a high standard of correctness.
However, existing theorem provers are unsuitable for mathematics. Their formal proofs are unreadable. They struggle to do simple tasks, such as evaluating limits. They lack much basic mathematics, and the material they do have is difficult to locate and apply.
ALEXANDRIA will create a proof development environment attractive to working mathematicians, utilising the best technology available across computer science. Its focus will be the management and use of large-scale mathematical knowledge, both theorems and algorithms. The project will employ mathematicians to investigate the formalisation of mathematics in practice. Our already substantial formalised libraries will serve as the starting point. They will be extended and annotated to support sophisticated searches. Techniques will be borrowed from machine learning, information retrieval and natural language processing. Algorithms will be treated similarly: ALEXANDRIA will help users find and invoke the proof methods and algorithms appropriate for the task.
ALEXANDRIA will provide (1) comprehensive formal mathematical libraries; (2) search within libraries, and the mining of libraries for proof patterns; (3) automated support for the construction of large formal proofs; (4) sound and practical computer algebra tools.
ALEXANDRIA will be based on legible structured proofs. Formal proofs should be not mere code, but a machine-checkable form of communication between mathematicians.
Summary
Mathematical proofs have always been prone to error. Today, proofs can be hundreds of pages long and combine results from many specialisms, making them almost impossible to check. One solution is to deploy modern verification technology. Interactive theorem provers have demonstrated their potential as vehicles for formalising mathematics through achievements such as the verification of the Kepler Conjecture. Proofs done using such tools reach a high standard of correctness.
However, existing theorem provers are unsuitable for mathematics. Their formal proofs are unreadable. They struggle to do simple tasks, such as evaluating limits. They lack much basic mathematics, and the material they do have is difficult to locate and apply.
ALEXANDRIA will create a proof development environment attractive to working mathematicians, utilising the best technology available across computer science. Its focus will be the management and use of large-scale mathematical knowledge, both theorems and algorithms. The project will employ mathematicians to investigate the formalisation of mathematics in practice. Our already substantial formalised libraries will serve as the starting point. They will be extended and annotated to support sophisticated searches. Techniques will be borrowed from machine learning, information retrieval and natural language processing. Algorithms will be treated similarly: ALEXANDRIA will help users find and invoke the proof methods and algorithms appropriate for the task.
ALEXANDRIA will provide (1) comprehensive formal mathematical libraries; (2) search within libraries, and the mining of libraries for proof patterns; (3) automated support for the construction of large formal proofs; (4) sound and practical computer algebra tools.
ALEXANDRIA will be based on legible structured proofs. Formal proofs should be not mere code, but a machine-checkable form of communication between mathematicians.
Max ERC Funding
2 430 140 €
Duration
Start date: 2017-09-01, End date: 2022-08-31
Project acronym ALGAME
Project Algorithms, Games, Mechanisms, and the Price of Anarchy
Researcher (PI) Elias Koutsoupias
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Advanced Grant (AdG), PE6, ERC-2012-ADG_20120216
Summary The objective of this proposal is to bring together a local team of young researchers who will work closely with international collaborators to advance the state of the art of Algorithmic Game Theory and open new venues of research at the interface of Computer Science, Game Theory, and Economics. The proposal consists mainly of three intertwined research strands: algorithmic mechanism design, price of anarchy, and online algorithms.
Specifically, we will attempt to resolve some outstanding open problems in algorithmic mechanism design: characterizing the incentive compatible mechanisms for important domains, such as the domain of combinatorial auctions, and resolving the approximation ratio of mechanisms for scheduling unrelated machines. More generally, we will study centralized and distributed algorithms whose inputs are controlled by selfish agents that are interested in the outcome of the computation. We will investigate new notions of mechanisms with strong truthfulness and limited susceptibility to externalities that can facilitate modular design of mechanisms of complex domains.
We will expand the current research on the price of anarchy to time-dependent games where the players can select not only how to act but also when to act. We also plan to resolve outstanding questions on the price of stability and to build a robust approach to these questions, similar to smooth analysis. For repeated games, we will investigate convergence of simple strategies (e.g., fictitious play), online fairness, and strategic considerations (e.g., metagames). More generally, our aim is to find a productive formulation of playing unknown games by drawing on the fields of online algorithms and machine learning.
Summary
The objective of this proposal is to bring together a local team of young researchers who will work closely with international collaborators to advance the state of the art of Algorithmic Game Theory and open new venues of research at the interface of Computer Science, Game Theory, and Economics. The proposal consists mainly of three intertwined research strands: algorithmic mechanism design, price of anarchy, and online algorithms.
Specifically, we will attempt to resolve some outstanding open problems in algorithmic mechanism design: characterizing the incentive compatible mechanisms for important domains, such as the domain of combinatorial auctions, and resolving the approximation ratio of mechanisms for scheduling unrelated machines. More generally, we will study centralized and distributed algorithms whose inputs are controlled by selfish agents that are interested in the outcome of the computation. We will investigate new notions of mechanisms with strong truthfulness and limited susceptibility to externalities that can facilitate modular design of mechanisms of complex domains.
We will expand the current research on the price of anarchy to time-dependent games where the players can select not only how to act but also when to act. We also plan to resolve outstanding questions on the price of stability and to build a robust approach to these questions, similar to smooth analysis. For repeated games, we will investigate convergence of simple strategies (e.g., fictitious play), online fairness, and strategic considerations (e.g., metagames). More generally, our aim is to find a productive formulation of playing unknown games by drawing on the fields of online algorithms and machine learning.
Max ERC Funding
2 461 000 €
Duration
Start date: 2013-04-01, End date: 2019-03-31
Project acronym ALUNIF
Project Algorithms and Lower Bounds: A Unified Approach
Researcher (PI) Rahul Santhanam
Host Institution (HI) THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD
Call Details Consolidator Grant (CoG), PE6, ERC-2013-CoG
Summary One of the fundamental goals of theoretical computer science is to
understand the possibilities and limits of efficient computation. This
quest has two dimensions. The
theory of algorithms focuses on finding efficient solutions to
problems, while computational complexity theory aims to understand when
and why problems are hard to solve. These two areas have different
philosophies and use different sets of techniques. However, in recent
years there have been indications of deep and mysterious connections
between them.
In this project, we propose to explore and develop the connections between
algorithmic analysis and complexity lower bounds in a systematic way.
On the one hand, we plan to use complexity lower bound techniques as inspiration
to design new and improved algorithms for Satisfiability and other
NP-complete problems, as well as to analyze existing algorithms better.
On the other hand, we plan to strengthen implications yielding circuit
lower bounds from non-trivial algorithms for Satisfiability, and to derive
new circuit lower bounds using these stronger implications.
This project has potential for massive impact in both the areas of algorithms
and computational complexity. Improved algorithms for Satisfiability could lead
to improved SAT solvers, and the new analytical tools would lead to a better
understanding of existing heuristics. Complexity lower bound questions are
fundamental
but notoriously difficult, and new lower bounds would open the way to
unconditionally secure cryptographic protocols and derandomization of
probabilistic algorithms. More broadly, this project aims to initiate greater
dialogue between the two areas, with an exchange of ideas and techniques
which leads to accelerated progress in both, as well as a deeper understanding
of the nature of efficient computation.
Summary
One of the fundamental goals of theoretical computer science is to
understand the possibilities and limits of efficient computation. This
quest has two dimensions. The
theory of algorithms focuses on finding efficient solutions to
problems, while computational complexity theory aims to understand when
and why problems are hard to solve. These two areas have different
philosophies and use different sets of techniques. However, in recent
years there have been indications of deep and mysterious connections
between them.
In this project, we propose to explore and develop the connections between
algorithmic analysis and complexity lower bounds in a systematic way.
On the one hand, we plan to use complexity lower bound techniques as inspiration
to design new and improved algorithms for Satisfiability and other
NP-complete problems, as well as to analyze existing algorithms better.
On the other hand, we plan to strengthen implications yielding circuit
lower bounds from non-trivial algorithms for Satisfiability, and to derive
new circuit lower bounds using these stronger implications.
This project has potential for massive impact in both the areas of algorithms
and computational complexity. Improved algorithms for Satisfiability could lead
to improved SAT solvers, and the new analytical tools would lead to a better
understanding of existing heuristics. Complexity lower bound questions are
fundamental
but notoriously difficult, and new lower bounds would open the way to
unconditionally secure cryptographic protocols and derandomization of
probabilistic algorithms. More broadly, this project aims to initiate greater
dialogue between the two areas, with an exchange of ideas and techniques
which leads to accelerated progress in both, as well as a deeper understanding
of the nature of efficient computation.
Max ERC Funding
1 274 496 €
Duration
Start date: 2014-03-01, End date: 2019-02-28
Project acronym ALZSYN
Project Imaging synaptic contributors to dementia
Researcher (PI) Tara Spires-Jones
Host Institution (HI) THE UNIVERSITY OF EDINBURGH
Call Details Consolidator Grant (CoG), LS5, ERC-2015-CoG
Summary Alzheimer's disease, the most common cause of dementia in older people, is a devastating condition that is becoming a public health crisis as our population ages. Despite great progress recently in Alzheimer’s disease research, we have no disease modifying drugs and a decade with a 99.6% failure rate of clinical trials attempting to treat the disease. This project aims to develop relevant therapeutic targets to restore brain function in Alzheimer’s disease by integrating human and model studies of synapses. It is widely accepted in the field that alterations in amyloid beta initiate the disease process. However the cascade leading from changes in amyloid to widespread tau pathology and neurodegeneration remain unclear. Synapse loss is the strongest pathological correlate of dementia in Alzheimer’s, and mounting evidence suggests that synapse degeneration plays a key role in causing cognitive decline. Here I propose to test the hypothesis that the amyloid cascade begins at the synapse leading to tau pathology, synapse dysfunction and loss, and ultimately neural circuit collapse causing cognitive impairment. The team will use cutting-edge multiphoton and array tomography imaging techniques to test mechanisms downstream of amyloid beta at synapses, and determine whether intervening in the cascade allows recovery of synapse structure and function. Importantly, I will combine studies in robust models of familial Alzheimer’s disease with studies in postmortem human brain to confirm relevance of our mechanistic studies to human disease. Finally, human stem cell derived neurons will be used to test mechanisms and potential therapeutics in neurons expressing the human proteome. Together, these experiments are ground-breaking since they have the potential to further our understanding of how synapses are lost in Alzheimer’s disease and to identify targets for effective therapeutic intervention, which is a critical unmet need in today’s health care system.
Summary
Alzheimer's disease, the most common cause of dementia in older people, is a devastating condition that is becoming a public health crisis as our population ages. Despite great progress recently in Alzheimer’s disease research, we have no disease modifying drugs and a decade with a 99.6% failure rate of clinical trials attempting to treat the disease. This project aims to develop relevant therapeutic targets to restore brain function in Alzheimer’s disease by integrating human and model studies of synapses. It is widely accepted in the field that alterations in amyloid beta initiate the disease process. However the cascade leading from changes in amyloid to widespread tau pathology and neurodegeneration remain unclear. Synapse loss is the strongest pathological correlate of dementia in Alzheimer’s, and mounting evidence suggests that synapse degeneration plays a key role in causing cognitive decline. Here I propose to test the hypothesis that the amyloid cascade begins at the synapse leading to tau pathology, synapse dysfunction and loss, and ultimately neural circuit collapse causing cognitive impairment. The team will use cutting-edge multiphoton and array tomography imaging techniques to test mechanisms downstream of amyloid beta at synapses, and determine whether intervening in the cascade allows recovery of synapse structure and function. Importantly, I will combine studies in robust models of familial Alzheimer’s disease with studies in postmortem human brain to confirm relevance of our mechanistic studies to human disease. Finally, human stem cell derived neurons will be used to test mechanisms and potential therapeutics in neurons expressing the human proteome. Together, these experiments are ground-breaking since they have the potential to further our understanding of how synapses are lost in Alzheimer’s disease and to identify targets for effective therapeutic intervention, which is a critical unmet need in today’s health care system.
Max ERC Funding
2 000 000 €
Duration
Start date: 2016-11-01, End date: 2021-10-31