Project acronym AMD
Project Algorithmic Mechanism Design: Beyond Truthful Mechanisms
Researcher (PI) Michal Feldman
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Starting Grant (StG), PE6, ERC-2013-StG
Summary "The first decade of Algorithmic Mechanism Design (AMD) concentrated, very successfully, on the design of truthful mechanisms for the allocation of resources among agents with private preferences.
Truthful mechanisms are ones that incentivize rational users to report their preferences truthfully.
Truthfulness, however, for all its theoretical appeal, suffers from several inherent limitations, mainly its high communication and computation complexities.
It is not surprising, therefore, that practical applications forego truthfulness and use simpler mechanisms instead.
Simplicity in itself, however, is not sufficient, as any meaningful mechanism should also have some notion of fairness; otherwise agents will stop using it over time.
In this project I plan to develop an innovative AMD theoretical framework that will go beyond truthfulness and focus instead on the natural themes of simplicity and fairness, in addition to computational tractability.
One of my primary goals will be the design of simple and fair poly-time mechanisms that perform at near optimal levels with respect to important economic objectives such as social welfare and revenue.
To this end, I will work toward providing precise definitions of simplicity and fairness and quantifying the effects of these restrictions on the performance levels that can be obtained.
A major challenge in the evaluation of non-truthful mechanisms is defining a reasonable behavior model that will enable their evaluation.
The success of this project could have a broad impact on Europe and beyond, as it would guide the design of natural mechanisms for markets of tens of billions of dollars in revenue, such as online advertising, or sales of wireless frequencies.
The timing of this project is ideal, as the AMD field is now sufficiently mature to lead to a breakthrough and at the same time young enough to be receptive to new approaches and themes."
Summary
"The first decade of Algorithmic Mechanism Design (AMD) concentrated, very successfully, on the design of truthful mechanisms for the allocation of resources among agents with private preferences.
Truthful mechanisms are ones that incentivize rational users to report their preferences truthfully.
Truthfulness, however, for all its theoretical appeal, suffers from several inherent limitations, mainly its high communication and computation complexities.
It is not surprising, therefore, that practical applications forego truthfulness and use simpler mechanisms instead.
Simplicity in itself, however, is not sufficient, as any meaningful mechanism should also have some notion of fairness; otherwise agents will stop using it over time.
In this project I plan to develop an innovative AMD theoretical framework that will go beyond truthfulness and focus instead on the natural themes of simplicity and fairness, in addition to computational tractability.
One of my primary goals will be the design of simple and fair poly-time mechanisms that perform at near optimal levels with respect to important economic objectives such as social welfare and revenue.
To this end, I will work toward providing precise definitions of simplicity and fairness and quantifying the effects of these restrictions on the performance levels that can be obtained.
A major challenge in the evaluation of non-truthful mechanisms is defining a reasonable behavior model that will enable their evaluation.
The success of this project could have a broad impact on Europe and beyond, as it would guide the design of natural mechanisms for markets of tens of billions of dollars in revenue, such as online advertising, or sales of wireless frequencies.
The timing of this project is ideal, as the AMD field is now sufficiently mature to lead to a breakthrough and at the same time young enough to be receptive to new approaches and themes."
Max ERC Funding
1 394 600 €
Duration
Start date: 2013-11-01, End date: 2018-10-31
Project acronym BACTERIAL SPORES
Project Investigating the Nature of Bacterial Spores
Researcher (PI) Sigal Ben-Yehuda
Host Institution (HI) THE HEBREW UNIVERSITY OF JERUSALEM
Call Details Starting Grant (StG), LS3, ERC-2007-StG
Summary When triggered by nutrient limitation, the Gram-positive bacterium Bacillus subtilis and its relatives enter a pathway of cellular differentiation culminating in the formation of a dormant cell type called a spore, the most resilient cell type known. Bacterial spores can survive for long periods of time and are able to endure extremes of heat, radiation and chemical assault. Remarkably, dormant spores can rapidly convert back to actively growing cells by a process called germination. Consequently, spore forming bacteria, including dangerous pathogens, (such as C. botulinum and B. anthracis) are highly resistant to antibacterial treatments and difficult to eradicate. Despite significant advances in our understanding of the process of spore formation, little is known about the nature of the mature spore. It is unrevealed how dormancy is maintained within the spore and how it is ceased, as the organization and the dynamics of the spore macromolecules remain obscure. The unusual biochemical and biophysical characteristics of the dormant spore make it a challenging biological system to investigate using conventional methods, and thus set the need to develop innovative approaches to study spore biology. We propose to explore the nature of spores by using B. subtilis as a primary experimental system. We intend to: (1) define the architecture of the spore chromosome, (2) track the complexity and fate of mRNA and protein molecules during sporulation, dormancy and germination, (3) revisit the basic notion of the spore dormancy (is it metabolically inert?), (4) compare the characteristics of bacilli spores from diverse ecophysiological groups, (5) investigate the features of spores belonging to distant bacterial genera, (6) generate an integrative database that categorizes the molecular features of spores. Our study will provide original insights and introduce novel concepts to the field of spore biology and may help devise innovative ways to combat spore forming pathogens.
Summary
When triggered by nutrient limitation, the Gram-positive bacterium Bacillus subtilis and its relatives enter a pathway of cellular differentiation culminating in the formation of a dormant cell type called a spore, the most resilient cell type known. Bacterial spores can survive for long periods of time and are able to endure extremes of heat, radiation and chemical assault. Remarkably, dormant spores can rapidly convert back to actively growing cells by a process called germination. Consequently, spore forming bacteria, including dangerous pathogens, (such as C. botulinum and B. anthracis) are highly resistant to antibacterial treatments and difficult to eradicate. Despite significant advances in our understanding of the process of spore formation, little is known about the nature of the mature spore. It is unrevealed how dormancy is maintained within the spore and how it is ceased, as the organization and the dynamics of the spore macromolecules remain obscure. The unusual biochemical and biophysical characteristics of the dormant spore make it a challenging biological system to investigate using conventional methods, and thus set the need to develop innovative approaches to study spore biology. We propose to explore the nature of spores by using B. subtilis as a primary experimental system. We intend to: (1) define the architecture of the spore chromosome, (2) track the complexity and fate of mRNA and protein molecules during sporulation, dormancy and germination, (3) revisit the basic notion of the spore dormancy (is it metabolically inert?), (4) compare the characteristics of bacilli spores from diverse ecophysiological groups, (5) investigate the features of spores belonging to distant bacterial genera, (6) generate an integrative database that categorizes the molecular features of spores. Our study will provide original insights and introduce novel concepts to the field of spore biology and may help devise innovative ways to combat spore forming pathogens.
Max ERC Funding
1 630 000 €
Duration
Start date: 2008-10-01, End date: 2013-09-30
Project acronym BANDWIDTH
Project The cost of limited communication bandwidth in distributed computing
Researcher (PI) Keren CENSOR-HILLEL
Host Institution (HI) TECHNION - ISRAEL INSTITUTE OF TECHNOLOGY
Call Details Starting Grant (StG), PE6, ERC-2017-STG
Summary Distributed systems underlie many modern technologies, a prime example being the Internet. The ever-increasing abundance of distributed systems necessitates their design and usage to be backed by strong theoretical foundations.
A major challenge that distributed systems face is the lack of a central authority, which brings many aspects of uncertainty into the environment, in the form of unknown network topology or unpredictable dynamic behavior. A practical restriction of distributed systems, which is at the heart of this proposal, is the limited bandwidth available for communication between the network components.
A central family of distributed tasks is that of local tasks, which are informally described as tasks which are possible to solve by sending information through only a relatively small number of hops. A cornerstone example is the need to break symmetry and provide a better utilization of resources, which can be obtained by the task of producing a valid coloring of the nodes given some small number of colors. Amazingly, there are still huge gaps between the known upper and lower bounds for the complexity of many local tasks. This holds even if one allows powerful assumptions of unlimited bandwidth. While some known algorithms indeed use small messages, the complexity gaps are even larger compared to the unlimited bandwidth case. This is not a mere coincidence, and in fact the existing theoretical infrastructure is provably incapable of
giving stronger lower bounds for many local tasks under limited bandwidth.
This proposal zooms in on this crucial blind spot in the current literature on the theory of distributed computing, namely, the study of local tasks under limited bandwidth. The goal of this research is to produce fast algorithms for fundamental distributed local tasks under restricted bandwidth, as well as understand their limitations by providing lower bounds.
Summary
Distributed systems underlie many modern technologies, a prime example being the Internet. The ever-increasing abundance of distributed systems necessitates their design and usage to be backed by strong theoretical foundations.
A major challenge that distributed systems face is the lack of a central authority, which brings many aspects of uncertainty into the environment, in the form of unknown network topology or unpredictable dynamic behavior. A practical restriction of distributed systems, which is at the heart of this proposal, is the limited bandwidth available for communication between the network components.
A central family of distributed tasks is that of local tasks, which are informally described as tasks which are possible to solve by sending information through only a relatively small number of hops. A cornerstone example is the need to break symmetry and provide a better utilization of resources, which can be obtained by the task of producing a valid coloring of the nodes given some small number of colors. Amazingly, there are still huge gaps between the known upper and lower bounds for the complexity of many local tasks. This holds even if one allows powerful assumptions of unlimited bandwidth. While some known algorithms indeed use small messages, the complexity gaps are even larger compared to the unlimited bandwidth case. This is not a mere coincidence, and in fact the existing theoretical infrastructure is provably incapable of
giving stronger lower bounds for many local tasks under limited bandwidth.
This proposal zooms in on this crucial blind spot in the current literature on the theory of distributed computing, namely, the study of local tasks under limited bandwidth. The goal of this research is to produce fast algorithms for fundamental distributed local tasks under restricted bandwidth, as well as understand their limitations by providing lower bounds.
Max ERC Funding
1 486 480 €
Duration
Start date: 2018-06-01, End date: 2023-05-31
Project acronym BeyondtheElite
Project Beyond the Elite: Jewish Daily Life in Medieval Europe
Researcher (PI) Elisheva Baumgarten
Host Institution (HI) THE HEBREW UNIVERSITY OF JERUSALEM
Call Details Consolidator Grant (CoG), SH6, ERC-2015-CoG
Summary The two fundamental challenges of this project are the integration of medieval Jewries and their histories within the framework of European history without undermining their distinct communal status and the creation of a history of everyday medieval Jewish life that includes those who were not part of the learned elite. The study will focus on the Jewish communities of northern Europe (roughly modern Germany, northern France and England) from 1100-1350. From the mid-thirteenth century these medieval Jewish communities were subject to growing persecution. The approaches proposed to access daily praxis seek to highlight tangible dimensions of religious life rather than the more common study of ideologies to date. This task is complex because the extant sources in Hebrew as well as those in Latin and vernacular were written by the learned elite and will require a broad survey of multiple textual and material sources.
Four main strands will be examined and combined:
1. An outline of the strata of Jewish society, better defining the elites and other groups.
2. A study of select communal and familial spaces such as the house, the synagogue, the market place have yet to be examined as social spaces.
3. Ritual and urban rhythms especially the annual cycle, connecting between Jewish and Christian environments.
4. Material culture, as objects were used by Jews and Christians alike.
Aspects of material culture, the physical environment and urban rhythms are often described as “neutral” yet will be mined to demonstrate how they exemplified difference while being simultaneously ubiquitous in local cultures. The deterioration of relations between Jews and Christians will provide a gauge for examining change during this period. The final stage of the project will include comparative case studies of other Jewish communities. I expect my findings will inform scholars of medieval culture at large and promote comparative methodologies for studying other minority ethnic groups
Summary
The two fundamental challenges of this project are the integration of medieval Jewries and their histories within the framework of European history without undermining their distinct communal status and the creation of a history of everyday medieval Jewish life that includes those who were not part of the learned elite. The study will focus on the Jewish communities of northern Europe (roughly modern Germany, northern France and England) from 1100-1350. From the mid-thirteenth century these medieval Jewish communities were subject to growing persecution. The approaches proposed to access daily praxis seek to highlight tangible dimensions of religious life rather than the more common study of ideologies to date. This task is complex because the extant sources in Hebrew as well as those in Latin and vernacular were written by the learned elite and will require a broad survey of multiple textual and material sources.
Four main strands will be examined and combined:
1. An outline of the strata of Jewish society, better defining the elites and other groups.
2. A study of select communal and familial spaces such as the house, the synagogue, the market place have yet to be examined as social spaces.
3. Ritual and urban rhythms especially the annual cycle, connecting between Jewish and Christian environments.
4. Material culture, as objects were used by Jews and Christians alike.
Aspects of material culture, the physical environment and urban rhythms are often described as “neutral” yet will be mined to demonstrate how they exemplified difference while being simultaneously ubiquitous in local cultures. The deterioration of relations between Jews and Christians will provide a gauge for examining change during this period. The final stage of the project will include comparative case studies of other Jewish communities. I expect my findings will inform scholars of medieval culture at large and promote comparative methodologies for studying other minority ethnic groups
Max ERC Funding
1 941 688 €
Duration
Start date: 2016-11-01, End date: 2021-10-31
Project acronym CAC
Project Cryptography and Complexity
Researcher (PI) Yuval Ishai
Host Institution (HI) TECHNION - ISRAEL INSTITUTE OF TECHNOLOGY
Call Details Starting Grant (StG), PE6, ERC-2010-StG_20091028
Summary Modern cryptography has deeply rooted connections with computational complexity theory and other areas of computer science. This proposal suggests to explore several {\em new connections} between questions in cryptography and questions from other domains, including computational complexity, coding theory, and even the natural sciences. The project is expected to broaden the impact of ideas from cryptography on other domains, and on the other hand to benefit cryptography by applying tools from other domains towards better solutions for central problems in cryptography.
Summary
Modern cryptography has deeply rooted connections with computational complexity theory and other areas of computer science. This proposal suggests to explore several {\em new connections} between questions in cryptography and questions from other domains, including computational complexity, coding theory, and even the natural sciences. The project is expected to broaden the impact of ideas from cryptography on other domains, and on the other hand to benefit cryptography by applying tools from other domains towards better solutions for central problems in cryptography.
Max ERC Funding
1 459 703 €
Duration
Start date: 2010-12-01, End date: 2015-11-30
Project acronym CAP
Project Computers Arguing with People
Researcher (PI) Sarit Kraus
Host Institution (HI) BAR ILAN UNIVERSITY
Call Details Advanced Grant (AdG), PE6, ERC-2010-AdG_20100224
Summary An important form of negotiation is argumentation. This is the ability to argue and to persuade the other party to accept a desired agreement, to acquire or give information, to coordinate goals and actions, and to find and verify evidence. This is a key capability in negotiating with humans.
While automated negotiations between software agents can often exchange offers and counteroffers, humans require persuasion. This challenges the design of agents arguing with people, with the objective that the outcome of the negotiation will meet the preferences of the arguer agent.
CAP’s objective is to enable automated agents to argue and persuade humans.
To achieve this, we intend to develop the following key components:
1) The extension of current game theory models of persuasion and bargaining to more realistic settings, 2) Algorithms and heuristics for generation and evaluation of arguments during negotiation with people, 3) Algorithms and heuristics for managing inconsistent views of the negotiation environment, and decision procedures for revelation, signalling, and requesting information, 4) The revision and update of the agent’s mental state and incorporation of social context, 5) Identifying strategies for expressing emotions in negotiations, 6) Technology for general opponent modelling from sparse and noisy data.
To demonstrate the developed methods, we will implement two training systems for people to improve their interviewing capabilities, and for training negotiators in inter-culture negotiations.
CAP will revolutionise the state of the art of automated systems negotiating with people. It will also create breakthroughs in the research of multi-agent systems in general, and will change paradigms by providing new directions for the way computers interact with people.
Summary
An important form of negotiation is argumentation. This is the ability to argue and to persuade the other party to accept a desired agreement, to acquire or give information, to coordinate goals and actions, and to find and verify evidence. This is a key capability in negotiating with humans.
While automated negotiations between software agents can often exchange offers and counteroffers, humans require persuasion. This challenges the design of agents arguing with people, with the objective that the outcome of the negotiation will meet the preferences of the arguer agent.
CAP’s objective is to enable automated agents to argue and persuade humans.
To achieve this, we intend to develop the following key components:
1) The extension of current game theory models of persuasion and bargaining to more realistic settings, 2) Algorithms and heuristics for generation and evaluation of arguments during negotiation with people, 3) Algorithms and heuristics for managing inconsistent views of the negotiation environment, and decision procedures for revelation, signalling, and requesting information, 4) The revision and update of the agent’s mental state and incorporation of social context, 5) Identifying strategies for expressing emotions in negotiations, 6) Technology for general opponent modelling from sparse and noisy data.
To demonstrate the developed methods, we will implement two training systems for people to improve their interviewing capabilities, and for training negotiators in inter-culture negotiations.
CAP will revolutionise the state of the art of automated systems negotiating with people. It will also create breakthroughs in the research of multi-agent systems in general, and will change paradigms by providing new directions for the way computers interact with people.
Max ERC Funding
2 334 057 €
Duration
Start date: 2011-07-01, End date: 2016-06-30
Project acronym CELLREPROGRAMMING
Project Uncovering the Mechanisms of Epigenetic Reprogramming of Pluripotent and Somatic Cell States
Researcher (PI) Yaqub Hanna
Host Institution (HI) WEIZMANN INSTITUTE OF SCIENCE
Call Details Starting Grant (StG), LS3, ERC-2011-StG_20101109
Summary The generation of animals by nuclear transfer demonstrated that the epigenetic state of somatic cells could be reset to an embryonic state, capable of directing the development of a new organism. The nuclear cloning technology is of interest for transplantation medicine, but any application is hampered by the inefficiency and ethical problems. A breakthrough solving these issues has been the in vitro derivation of reprogrammed Induced Pluripotent Stem “iPS” cells by the ectopic expression of defined transcription factors in somatic cells. iPS cells recapitulate all defining features of embryo-derived pluripotent stem cells, including the ability to differentiate into all somatic cell types. Further, recent publications have demonstrated the ability to directly trans-differentiate somatic cell types by ectopic expression of lineage specification factors. Thus, it is becoming increasingly clear that an ultimate goal in the stem cell field is to enable scientists to have the power to safely manipulate somatic cells by “reprogramming” their behavior at will. However, to frame this challenge, we must understand the basic mechanisms underlying the generation of reprogrammed cells in parallel to designing strategies for their medical application and their use in human disease specific research. In this ERC Starting Grant proposal, I describe comprehensive lines of experimentation that I plan to conduct in my new lab scheduled to open in April 2011 at the Weizmann Institute of Science. We will utilize exacting transgenic mammalian models and high throughput sequencing and genomic screening tools for in depth characterization of the molecular “rules” of rewiring the epigenome of somatic and pluripotent cell states. The proposed research endeavors will not only contribute to the development of safer strategies for cell reprogramming, but will also help decipher how diverse gene expression programs lead to cellular specification during normal development.
Summary
The generation of animals by nuclear transfer demonstrated that the epigenetic state of somatic cells could be reset to an embryonic state, capable of directing the development of a new organism. The nuclear cloning technology is of interest for transplantation medicine, but any application is hampered by the inefficiency and ethical problems. A breakthrough solving these issues has been the in vitro derivation of reprogrammed Induced Pluripotent Stem “iPS” cells by the ectopic expression of defined transcription factors in somatic cells. iPS cells recapitulate all defining features of embryo-derived pluripotent stem cells, including the ability to differentiate into all somatic cell types. Further, recent publications have demonstrated the ability to directly trans-differentiate somatic cell types by ectopic expression of lineage specification factors. Thus, it is becoming increasingly clear that an ultimate goal in the stem cell field is to enable scientists to have the power to safely manipulate somatic cells by “reprogramming” their behavior at will. However, to frame this challenge, we must understand the basic mechanisms underlying the generation of reprogrammed cells in parallel to designing strategies for their medical application and their use in human disease specific research. In this ERC Starting Grant proposal, I describe comprehensive lines of experimentation that I plan to conduct in my new lab scheduled to open in April 2011 at the Weizmann Institute of Science. We will utilize exacting transgenic mammalian models and high throughput sequencing and genomic screening tools for in depth characterization of the molecular “rules” of rewiring the epigenome of somatic and pluripotent cell states. The proposed research endeavors will not only contribute to the development of safer strategies for cell reprogramming, but will also help decipher how diverse gene expression programs lead to cellular specification during normal development.
Max ERC Funding
1 960 000 €
Duration
Start date: 2011-11-01, End date: 2016-10-31
Project acronym CLC
Project Cryptography with Low Complexity
Researcher (PI) Benny Applebaum
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Starting Grant (StG), PE6, ERC-2014-STG
Summary The efficiency of cryptographic constructions is a fundamental question. Theoretically, it is important to understand how much computational resources are needed to guarantee strong notions of security. Practically, highly efficient schemes are always desirable for real-world applications. More generally, the possibility of cryptography with low complexity has wide applications for problems in computational complexity, combinatorial optimization, and computational learning theory.
In this proposal we aim to understand what are the minimal computational resources needed to perform basic cryptographic tasks. In a nutshell, we suggest to focus on three main objectives. First, we would like to get better understanding of the cryptographic hardness of random local functions. Such functions can be computed by highly-efficient circuits and their cryptographic hardness provides a strong and clean formulation for the conjectured average-case hardness of constraint satisfaction problems - a fundamental subject which lies at the core of the theory of computer science. Our second objective is to harness our insights into the hardness of local functions to improve the efficiency of basic cryptographic building blocks such as pseudorandom functions. Finally, our third objective is to expand our theoretical understanding of garbled circuits, study their limitations, and improve their efficiency.
The suggested project can bridge across different regions of computer science such as random combinatorial structures, cryptography, and circuit complexity. It is expected to impact central problems in cryptography, while enriching the general landscape of theoretical computer science.
Summary
The efficiency of cryptographic constructions is a fundamental question. Theoretically, it is important to understand how much computational resources are needed to guarantee strong notions of security. Practically, highly efficient schemes are always desirable for real-world applications. More generally, the possibility of cryptography with low complexity has wide applications for problems in computational complexity, combinatorial optimization, and computational learning theory.
In this proposal we aim to understand what are the minimal computational resources needed to perform basic cryptographic tasks. In a nutshell, we suggest to focus on three main objectives. First, we would like to get better understanding of the cryptographic hardness of random local functions. Such functions can be computed by highly-efficient circuits and their cryptographic hardness provides a strong and clean formulation for the conjectured average-case hardness of constraint satisfaction problems - a fundamental subject which lies at the core of the theory of computer science. Our second objective is to harness our insights into the hardness of local functions to improve the efficiency of basic cryptographic building blocks such as pseudorandom functions. Finally, our third objective is to expand our theoretical understanding of garbled circuits, study their limitations, and improve their efficiency.
The suggested project can bridge across different regions of computer science such as random combinatorial structures, cryptography, and circuit complexity. It is expected to impact central problems in cryptography, while enriching the general landscape of theoretical computer science.
Max ERC Funding
1 265 750 €
Duration
Start date: 2015-05-01, End date: 2021-04-30
Project acronym COHOMCODES
Project Robust Codes from Higher Dimesional Expanders
Researcher (PI) Tali Kaufman Halman
Host Institution (HI) BAR ILAN UNIVERSITY
Call Details Starting Grant (StG), PE6, ERC-2013-StG
Summary Error correcting codes play a fundamental role in computer science. Good codes are codes with rate and distance that are asymptotically optimal. Some of the most successful good codes are constructed using expander graphs. In recent years a new notion of {\em robust} error correcting codes, known as locally testable codes (LTCs), has emerged. Locally testable codes are codes in which a proximity of a vector to an error correcting code can be achieved by probing the vector in {\em constant} many locations (independent of its length). LTCs are at the heart of Probabilistically Checkable Proofs (PCPs) and their construction has been sought since the discovery of the PCP theorem in the early 1990s.
Despite 20 years of research, it is still widely open whether good locally testable codes exist. LTCs present completely new challenge to the field of error correcting codes. In the old paradigm a random code is a good code and the main focus was to construct explicit codes that imitate the random code. However, a random code is not an LTC. Thus, contrary to traditional codes, there are no natural candidates for LTCs. The known constructions of robust codes are ad hoc, and there is a lack of theory that explains their existence.
The goal of the current research plan is to harness the emerging field of higher dimensional expanders and their topological properties for a systematic study of robust error correcting codes. Higher dimensional expanders are natural candidates for obtaining robust codes since they offer a strong form of redundancy that is essential for robustness. Such form of redundancy is lacking by their one dimensional analogue (i.e., expander graphs). Hence, the known expander codes are not robust. We expect that our study will draw new connections between error correcting codes, high dimensional expanders, topology and probability that will shed new light on these fields, and in particular, will advance the constructing of good and robust codes.
Summary
Error correcting codes play a fundamental role in computer science. Good codes are codes with rate and distance that are asymptotically optimal. Some of the most successful good codes are constructed using expander graphs. In recent years a new notion of {\em robust} error correcting codes, known as locally testable codes (LTCs), has emerged. Locally testable codes are codes in which a proximity of a vector to an error correcting code can be achieved by probing the vector in {\em constant} many locations (independent of its length). LTCs are at the heart of Probabilistically Checkable Proofs (PCPs) and their construction has been sought since the discovery of the PCP theorem in the early 1990s.
Despite 20 years of research, it is still widely open whether good locally testable codes exist. LTCs present completely new challenge to the field of error correcting codes. In the old paradigm a random code is a good code and the main focus was to construct explicit codes that imitate the random code. However, a random code is not an LTC. Thus, contrary to traditional codes, there are no natural candidates for LTCs. The known constructions of robust codes are ad hoc, and there is a lack of theory that explains their existence.
The goal of the current research plan is to harness the emerging field of higher dimensional expanders and their topological properties for a systematic study of robust error correcting codes. Higher dimensional expanders are natural candidates for obtaining robust codes since they offer a strong form of redundancy that is essential for robustness. Such form of redundancy is lacking by their one dimensional analogue (i.e., expander graphs). Hence, the known expander codes are not robust. We expect that our study will draw new connections between error correcting codes, high dimensional expanders, topology and probability that will shed new light on these fields, and in particular, will advance the constructing of good and robust codes.
Max ERC Funding
1 302 000 €
Duration
Start date: 2014-02-01, End date: 2020-01-31
Project acronym CombiCompGeom
Project Combinatorial Aspects of Computational Geometry
Researcher (PI) Natan Rubin
Host Institution (HI) BEN-GURION UNIVERSITY OF THE NEGEV
Call Details Starting Grant (StG), PE6, ERC-2015-STG
Summary The project focuses on the interface between computational and combinatorial geometry.
Geometric problems emerge in a variety of computational fields that interact with the physical world.
The performance of geometric algorithms is determined by the description complexity of their underlying combinatorial structures. Hence, most theoretical challenges faced by computational geometry are of a distinctly combinatorial nature.
In the past two decades, computational geometry has been revolutionized by the powerful combination of random sampling techniques with the abstract machinery of geometric arrangements. These insights were used, in turn, to establish state-of-the-art results in combinatorial geometry. Nevertheless, a number of fundamental problems remained open and resisted numerous attempts to solve them.
Motivated by the recent breakthrough results, in which the PI played a central role, we propose two exciting lines of study with the potential to change the landscape of this field.
The first research direction concerns the complexity of Voronoi diagrams -- arguably the most common structures in computational geometry.
The second direction concerns combinatorial and algorithmic aspects of geometric intersection structures, including some fundamental open problems in geometric transversal theory. Many of these questions are motivated by geometric variants of general covering and packing problems, and all efficient approximation schemes for them must rely on the intrinsic properties of geometric graphs and hypergraphs.
Any progress in responding to these challenges will constitute a major breakthrough in both computational and combinatorial geometry.
Summary
The project focuses on the interface between computational and combinatorial geometry.
Geometric problems emerge in a variety of computational fields that interact with the physical world.
The performance of geometric algorithms is determined by the description complexity of their underlying combinatorial structures. Hence, most theoretical challenges faced by computational geometry are of a distinctly combinatorial nature.
In the past two decades, computational geometry has been revolutionized by the powerful combination of random sampling techniques with the abstract machinery of geometric arrangements. These insights were used, in turn, to establish state-of-the-art results in combinatorial geometry. Nevertheless, a number of fundamental problems remained open and resisted numerous attempts to solve them.
Motivated by the recent breakthrough results, in which the PI played a central role, we propose two exciting lines of study with the potential to change the landscape of this field.
The first research direction concerns the complexity of Voronoi diagrams -- arguably the most common structures in computational geometry.
The second direction concerns combinatorial and algorithmic aspects of geometric intersection structures, including some fundamental open problems in geometric transversal theory. Many of these questions are motivated by geometric variants of general covering and packing problems, and all efficient approximation schemes for them must rely on the intrinsic properties of geometric graphs and hypergraphs.
Any progress in responding to these challenges will constitute a major breakthrough in both computational and combinatorial geometry.
Max ERC Funding
1 303 750 €
Duration
Start date: 2016-09-01, End date: 2021-08-31