Project acronym PCPABF
Project Challenging Computational Infeasibility: PCP and Boolean functions
Researcher (PI) Shmuel Avraham Safra
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE6, ERC-2018-ADG
Summary Computer Science, in particular, Analysis of Algorithms and Computational-Complexity theory, classify algorithmic-problems into feasible ones and those that cannot be efficiently-solved. Many fundamental problems were shown NP-hard, therefore, unless P=NP, they are infeasible.
Consequently, research efforts shifted towards approximation algorithms, which find close-to-optimal solutions for NP-hard optimization problems.
The PCP Theorem and its application to infeasibility of approximation establish that, unless P=NP, there are no efficient approximation algorithms for numerous classical problems; research that won the authors --the PI included-- the 2001 Godel prize.
To show infeasibility of approximation of some fundamental problems, however, a stronger PCP was postulated in 2002, namely, Khot's Unique-Games Conjecture.
It has transformed our understanding of optimization problems, provoked new tools in order to refute it and motivating new sophisticated techniques aimed at proving it.
Recently Khot, Minzer (a student of the PI) and the PI proved a related conjecture: the 2-to-2-Games conjecture (our paper just won Best Paper award at FOCS'18). In light of that progress, recognized by the community as half the distance towards the Unique-Games conjecture, resolving the Unique-Games conjecture seems much more likely.
A field that plays a crucial role in this progress is Analysis of Boolean-functions.
For the recent breakthrough we had to dive deep into expansion properties of the Grassmann-graph.
The insight was subsequently applied to achieve much awaited progress on fundamental properties of the Johnson-graph.
With the emergence of cloud-computing, cryptocurrency, public-ledger and Blockchain technologies, the PCP methodology has found new and exciting applications.
This framework governs SNARKs, which is a new, emerging technology, and the ZCASH technology on top of Blockchain.
This is a thriving research area, but also an extremely vibrant High-Tech sector.
Summary
Computer Science, in particular, Analysis of Algorithms and Computational-Complexity theory, classify algorithmic-problems into feasible ones and those that cannot be efficiently-solved. Many fundamental problems were shown NP-hard, therefore, unless P=NP, they are infeasible.
Consequently, research efforts shifted towards approximation algorithms, which find close-to-optimal solutions for NP-hard optimization problems.
The PCP Theorem and its application to infeasibility of approximation establish that, unless P=NP, there are no efficient approximation algorithms for numerous classical problems; research that won the authors --the PI included-- the 2001 Godel prize.
To show infeasibility of approximation of some fundamental problems, however, a stronger PCP was postulated in 2002, namely, Khot's Unique-Games Conjecture.
It has transformed our understanding of optimization problems, provoked new tools in order to refute it and motivating new sophisticated techniques aimed at proving it.
Recently Khot, Minzer (a student of the PI) and the PI proved a related conjecture: the 2-to-2-Games conjecture (our paper just won Best Paper award at FOCS'18). In light of that progress, recognized by the community as half the distance towards the Unique-Games conjecture, resolving the Unique-Games conjecture seems much more likely.
A field that plays a crucial role in this progress is Analysis of Boolean-functions.
For the recent breakthrough we had to dive deep into expansion properties of the Grassmann-graph.
The insight was subsequently applied to achieve much awaited progress on fundamental properties of the Johnson-graph.
With the emergence of cloud-computing, cryptocurrency, public-ledger and Blockchain technologies, the PCP methodology has found new and exciting applications.
This framework governs SNARKs, which is a new, emerging technology, and the ZCASH technology on top of Blockchain.
This is a thriving research area, but also an extremely vibrant High-Tech sector.
Max ERC Funding
2 059 375 €
Duration
Start date: 2019-10-01, End date: 2024-09-30
Project acronym PREPROCESSING
Project RIGOROUS THEORY OF PREPROCESSING
Researcher (PI) Fedor Fomin
Host Institution (HI) UNIVERSITETET I BERGEN
Call Details Advanced Grant (AdG), PE6, ERC-2010-AdG_20100224
Summary The main research goal of this project is the quest for rigorous mathematical theory explaining the power and failure of heuristics. The incapability of current computational models to explain the success of heuristic algorithms in practical computing is the subject of wide discussion for more than four decades. Within this project we expect a significant breakthrough in the study of a large family of heuristics: Preprocessing (data reduction or kernelization). Preprocessing is a reduction of the problem to a simpler one and this is the type of algorithms used in almost every application.
As key to novel and groundbreaking results, the proposed project aims to develop new theory of polynomial time compressibility. Understanding the origin of compressibility will serve to build more powerful heuristic algorithms, as well as to explain the behaviour of preprocessing.
The ubiquity of preprocessing makes the theory of compressibility extremely important.
The new theory will be able to transfer the ideas of efficient computation beyond the established borders.
Summary
The main research goal of this project is the quest for rigorous mathematical theory explaining the power and failure of heuristics. The incapability of current computational models to explain the success of heuristic algorithms in practical computing is the subject of wide discussion for more than four decades. Within this project we expect a significant breakthrough in the study of a large family of heuristics: Preprocessing (data reduction or kernelization). Preprocessing is a reduction of the problem to a simpler one and this is the type of algorithms used in almost every application.
As key to novel and groundbreaking results, the proposed project aims to develop new theory of polynomial time compressibility. Understanding the origin of compressibility will serve to build more powerful heuristic algorithms, as well as to explain the behaviour of preprocessing.
The ubiquity of preprocessing makes the theory of compressibility extremely important.
The new theory will be able to transfer the ideas of efficient computation beyond the established borders.
Max ERC Funding
2 227 051 €
Duration
Start date: 2011-04-01, End date: 2016-03-31
Project acronym PROGEOCOM
Project Avenues in Probabilistic and Geometric Combinatorics
Researcher (PI) Gil Kalai
Host Institution (HI) THE HEBREW UNIVERSITY OF JERUSALEM
Call Details Advanced Grant (AdG), PE1, ERC-2012-ADG_20120216
Summary We consider problems in geometric and probabilistic combinatorics and discuss some applications to and connections with other areas.One underlying theme of our proposal is discrete isoperimetric relations.
On the probabilistic side we discuss applications of Fourier analysis of Boolean functions to the study of threshold behavior of random graphs and other stochastic models, and propose ten directions for this emerging theory. One crucial problem is the study of near equality cases of Harper's isoperimetric inequality.
On the geometric side we discuss the relation between the number of (k-1)-dimensional faces and the number of k-dimensional faces for complexes that can be embedded in 2k-dimensions. We also consider metrical and algorithmical problems on graphs of polytopes and Helly-type theorems.
Summary
We consider problems in geometric and probabilistic combinatorics and discuss some applications to and connections with other areas.One underlying theme of our proposal is discrete isoperimetric relations.
On the probabilistic side we discuss applications of Fourier analysis of Boolean functions to the study of threshold behavior of random graphs and other stochastic models, and propose ten directions for this emerging theory. One crucial problem is the study of near equality cases of Harper's isoperimetric inequality.
On the geometric side we discuss the relation between the number of (k-1)-dimensional faces and the number of k-dimensional faces for complexes that can be embedded in 2k-dimensions. We also consider metrical and algorithmical problems on graphs of polytopes and Helly-type theorems.
Max ERC Funding
1 376 504 €
Duration
Start date: 2013-05-01, End date: 2018-04-30
Project acronym RandomZeroSets
Project Zero sets of random functions
Researcher (PI) Mikhail SODIN
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE1, ERC-2015-AdG
Summary "The proposed research is focused on zero sets of random functions.
This is a rapidly growing area that lies at the crossroads of analysis,
probability theory and mathematical physics. Various instances of zero
sets of random functions have been used to model different phenomena
in quantum chaos, complex analysis, real algebraic geometry, and
theory of random point processes.
The proposal consists of three parts. The first one deals with asymptotic
topology of zero sets of smooth random functions of several real variables.
This can be viewed as a statistical counterpart of the first half of Hilbert's 16th
problem. At the same time, it is closely related to percolation theory.
In the second and third parts, we turn to zero sets of random analytic functions
of one complex variable. The zero sets studied in the second part provide one
of few natural instances of a homogeneous point process with suppressed
fluctuations and strong short-range interactions. These point processes have
many features, which are in striking contrast with the ones of the Poisson point
process. One of these features is the coexistence of different Gaussian scaling
limits for different linear statistics.
The third part deals with zeroes of Taylor series with random and pseudo-random
coefficients. Studying these zero sets should shed light on the relation between
the distribution of coefficients of a Taylor series and the distribution of its zeroes,
which is still ""terra incognita'' of classical complex analysis."
Summary
"The proposed research is focused on zero sets of random functions.
This is a rapidly growing area that lies at the crossroads of analysis,
probability theory and mathematical physics. Various instances of zero
sets of random functions have been used to model different phenomena
in quantum chaos, complex analysis, real algebraic geometry, and
theory of random point processes.
The proposal consists of three parts. The first one deals with asymptotic
topology of zero sets of smooth random functions of several real variables.
This can be viewed as a statistical counterpart of the first half of Hilbert's 16th
problem. At the same time, it is closely related to percolation theory.
In the second and third parts, we turn to zero sets of random analytic functions
of one complex variable. The zero sets studied in the second part provide one
of few natural instances of a homogeneous point process with suppressed
fluctuations and strong short-range interactions. These point processes have
many features, which are in striking contrast with the ones of the Poisson point
process. One of these features is the coexistence of different Gaussian scaling
limits for different linear statistics.
The third part deals with zeroes of Taylor series with random and pseudo-random
coefficients. Studying these zero sets should shed light on the relation between
the distribution of coefficients of a Taylor series and the distribution of its zeroes,
which is still ""terra incognita'' of classical complex analysis."
Max ERC Funding
1 658 750 €
Duration
Start date: 2016-10-01, End date: 2021-09-30
Project acronym RMAST
Project Random Models in Arithmetic and Spectral Theory
Researcher (PI) Zeev Rudnick
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE1, ERC-2017-ADG
Summary The proposal studies deterministic problems in the spectral theory of the Laplacian and in analytic number theory by using random models. I propose two projects in spectral theory on this theme, both with a strong arithmetic ingredient, the first about minimal gaps between the eigenvalues of the Laplacian, where I seek a fit with the corresponding quantities for the various conjectured universality classes (Poisson/GUE/GOE), and the second about curvature measures of nodal lines of eigenfunctions of the Laplacian, where I seek to determine the size of the curvature measures for the large eigenvalue limit. The third project originates in analytic number theory, on angular distribution of prime ideals in number fields, function field analogues and connections with Random Matrix Theory, where I raise new conjectures and problems on a very classical subject, and aim to resolve them at least in the function field setting.
Summary
The proposal studies deterministic problems in the spectral theory of the Laplacian and in analytic number theory by using random models. I propose two projects in spectral theory on this theme, both with a strong arithmetic ingredient, the first about minimal gaps between the eigenvalues of the Laplacian, where I seek a fit with the corresponding quantities for the various conjectured universality classes (Poisson/GUE/GOE), and the second about curvature measures of nodal lines of eigenfunctions of the Laplacian, where I seek to determine the size of the curvature measures for the large eigenvalue limit. The third project originates in analytic number theory, on angular distribution of prime ideals in number fields, function field analogues and connections with Random Matrix Theory, where I raise new conjectures and problems on a very classical subject, and aim to resolve them at least in the function field setting.
Max ERC Funding
1 840 625 €
Duration
Start date: 2019-02-01, End date: 2024-01-31
Project acronym SensStabComp
Project Sensitivity, Stability, and Computation
Researcher (PI) Gil KALAI
Host Institution (HI) INTERDISCIPLINARY CENTER (IDC) HERZLIYA
Call Details Advanced Grant (AdG), PE1, ERC-2018-ADG
Summary Noise sensitivity and noise stability of Boolean functions, percolation, and other models were introduced in a paper by Benjamini, Kalai, and Schramm (1999) and were extensively studied in the last two decades. We propose to extend this study to various stochastic and combinatorial models, and to explore connections with computer science, quantum information, voting methods and other areas.
The first goal of our proposed project is to push the mathematical theory of noise stability and noise sensitivity forward for various
models in probabilistic combinatorics and statistical physics. A main mathematical tool, going back to Kahn, Kalai, and Linial (1988),
is applications of (high-dimensional) Fourier methods, and our second goal is to extend and develop these discrete Fourier methods.
Our third goal is to find applications toward central old-standing problems in combinatorics, probability and the theory of computing.
The fourth goal of our project is to further develop the ``argument against quantum computers'' which is based on the insight that noisy intermediate scale quantum computing is noise stable. This follows the work of Kalai and Kindler (2014) for the case of noisy non-interacting bosons. The fifth goal of our proposal is to enrich our mathematical understanding and to apply it, by studying connections of the theory with various areas of theoretical computer science, and with the theory of social choice.
Summary
Noise sensitivity and noise stability of Boolean functions, percolation, and other models were introduced in a paper by Benjamini, Kalai, and Schramm (1999) and were extensively studied in the last two decades. We propose to extend this study to various stochastic and combinatorial models, and to explore connections with computer science, quantum information, voting methods and other areas.
The first goal of our proposed project is to push the mathematical theory of noise stability and noise sensitivity forward for various
models in probabilistic combinatorics and statistical physics. A main mathematical tool, going back to Kahn, Kalai, and Linial (1988),
is applications of (high-dimensional) Fourier methods, and our second goal is to extend and develop these discrete Fourier methods.
Our third goal is to find applications toward central old-standing problems in combinatorics, probability and the theory of computing.
The fourth goal of our project is to further develop the ``argument against quantum computers'' which is based on the insight that noisy intermediate scale quantum computing is noise stable. This follows the work of Kalai and Kindler (2014) for the case of noisy non-interacting bosons. The fifth goal of our proposal is to enrich our mathematical understanding and to apply it, by studying connections of the theory with various areas of theoretical computer science, and with the theory of social choice.
Max ERC Funding
1 754 500 €
Duration
Start date: 2019-06-01, End date: 2024-05-31
Project acronym SMALLOSTERY
Project Single-molecule spectroscopy of coordinated motions in allosteric proteins
Researcher (PI) Gilad HARAN
Host Institution (HI) WEIZMANN INSTITUTE OF SCIENCE
Call Details Advanced Grant (AdG), PE4, ERC-2016-ADG
Summary Critical for the function of many proteins, allosteric communication involves transmission of the effect of binding at one site of a protein to another through conformational changes. Yet the structural and dynamic basis for allostery remains poorly understood. In particular, there is no method to follow coordinated large-scale motions of domains and subunits in proteins as they occur. Since the subunits of allosteric proteins often contain multiple domains, any such method entails probing the dynamics along several intra-protein distances simultaneously.
This proposal aims at ameliorating this deficiency by creating the experimental framework for exploring time-dependent coordination of allosteric transitions of multiple units within proteins. Our methodology will rely on single-molecule FRET spectroscopy with multiple labels on the same protein and advanced analysis. We will explore fundamental issues in protein dynamics: relative motions of domains within subunits, propagation of conformational change between subunits, and synchronization of these motions by effector molecules.
To investigate these issues, we have carefully selected three model systems, each representing an important scenario of allosteric regulation. While the homo-oligomeric protein-folder GroEL conserves symmetry in a concerted transition between major structural states, the symmetry of the homo-oligomeric disaggregating machine ClpB is broken via a sequential transition. Symmetry is attained only after binding to DNA and ligands in the third system, the family of RXR heterodimers.
This exciting project will provide the very first catalogue of coordinated and time-ordered motions within and between subunits of allosteric proteins and the first measurement of the time scale of the conformational spread through a large protein. It will enhance dramatically our understanding of how allostery contributes to protein function, influencing future efforts to design drugs for allosteric proteins.
Summary
Critical for the function of many proteins, allosteric communication involves transmission of the effect of binding at one site of a protein to another through conformational changes. Yet the structural and dynamic basis for allostery remains poorly understood. In particular, there is no method to follow coordinated large-scale motions of domains and subunits in proteins as they occur. Since the subunits of allosteric proteins often contain multiple domains, any such method entails probing the dynamics along several intra-protein distances simultaneously.
This proposal aims at ameliorating this deficiency by creating the experimental framework for exploring time-dependent coordination of allosteric transitions of multiple units within proteins. Our methodology will rely on single-molecule FRET spectroscopy with multiple labels on the same protein and advanced analysis. We will explore fundamental issues in protein dynamics: relative motions of domains within subunits, propagation of conformational change between subunits, and synchronization of these motions by effector molecules.
To investigate these issues, we have carefully selected three model systems, each representing an important scenario of allosteric regulation. While the homo-oligomeric protein-folder GroEL conserves symmetry in a concerted transition between major structural states, the symmetry of the homo-oligomeric disaggregating machine ClpB is broken via a sequential transition. Symmetry is attained only after binding to DNA and ligands in the third system, the family of RXR heterodimers.
This exciting project will provide the very first catalogue of coordinated and time-ordered motions within and between subunits of allosteric proteins and the first measurement of the time scale of the conformational spread through a large protein. It will enhance dramatically our understanding of how allostery contributes to protein function, influencing future efforts to design drugs for allosteric proteins.
Max ERC Funding
2 484 722 €
Duration
Start date: 2017-05-01, End date: 2022-04-30
Project acronym STACKSRTFPERIODS
Project Stacks in Representation Theory, Relative Trace Formula and analysis of Automorphic Periods
Researcher (PI) Joseph Bernstein
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE1, ERC-2011-ADG_20110209
Summary "One of the central problems in number theory is to prove some
reasonably sharp bounds for values of $L$-functions and of
corresponding automorphic periods (they are usually called ""subconvexity
bounds""). In this project I propose to study two new tools
in representation theory of reductive groups over local fields
-- Densities on Stcks and Mirolocalization of representtions.
I am going to use these tools to obtain very strong subconvexity bounds
for periods of automorphic representations. This is an extension
of my recent work with A. Reznikov where we established these
bounds in some special case.
These tools will also have many other applications to problems
in Representation theory and the theory of automorphic forms
(e.g. Langlands' functoriality conjecture)."
Summary
"One of the central problems in number theory is to prove some
reasonably sharp bounds for values of $L$-functions and of
corresponding automorphic periods (they are usually called ""subconvexity
bounds""). In this project I propose to study two new tools
in representation theory of reductive groups over local fields
-- Densities on Stcks and Mirolocalization of representtions.
I am going to use these tools to obtain very strong subconvexity bounds
for periods of automorphic representations. This is an extension
of my recent work with A. Reznikov where we established these
bounds in some special case.
These tools will also have many other applications to problems
in Representation theory and the theory of automorphic forms
(e.g. Langlands' functoriality conjecture)."
Max ERC Funding
1 179 000 €
Duration
Start date: 2012-03-01, End date: 2017-08-31
Project acronym SYMPTOPODYNQUANT
Project Symplectic topology and its interactions: from dynamics to quantization
Researcher (PI) Leonid Polterovich
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE1, ERC-2013-ADG
Summary "The proposed research belongs to symplectic topology, a rapidly developing
field of mathematics which originally appeared as a geometric tool for problems of classical mechanics. Since the 1980ies, new powerful methods such as theory of pseudo-holomorphic curves, Morse-Floer theory on loop spaces, symplectic field theory and mirror symmetry changed the face of the field and put it at the crossroads of several mathematical disciplines. In this proposal I develop function theory on symplectic manifolds, a recently emerged subject providing new tools and an alternative intuition in the field. With these tools, I explore footprints of symplectic rigidity in quantum mechanics, a brand new playground for applications of ``hard"" symplectic methods. This enterprise should bring novel insights into both fields. Other proposed applications of function theory on symplectic manifolds include Hamiltonian dynamics and Lagrangian knots. Function theory on symplectic manifolds is fruitfully interacting with geometry and algebra of groups of symplectic and contact transformations, which form another objective of this proposal. I focus on distortion of cyclic subgroups, quasi-morphisms and restrictions on finitely generated subgroups including the symplectic and contact versions of the Zimmer program. In the contact case, this subject is making nowadays its very first steps and is essentially unexplored. The progress in this direction will shed new light on the structure of these transformation groups playing a fundamental role in geometry, topology and dynamics."
Summary
"The proposed research belongs to symplectic topology, a rapidly developing
field of mathematics which originally appeared as a geometric tool for problems of classical mechanics. Since the 1980ies, new powerful methods such as theory of pseudo-holomorphic curves, Morse-Floer theory on loop spaces, symplectic field theory and mirror symmetry changed the face of the field and put it at the crossroads of several mathematical disciplines. In this proposal I develop function theory on symplectic manifolds, a recently emerged subject providing new tools and an alternative intuition in the field. With these tools, I explore footprints of symplectic rigidity in quantum mechanics, a brand new playground for applications of ``hard"" symplectic methods. This enterprise should bring novel insights into both fields. Other proposed applications of function theory on symplectic manifolds include Hamiltonian dynamics and Lagrangian knots. Function theory on symplectic manifolds is fruitfully interacting with geometry and algebra of groups of symplectic and contact transformations, which form another objective of this proposal. I focus on distortion of cyclic subgroups, quasi-morphisms and restrictions on finitely generated subgroups including the symplectic and contact versions of the Zimmer program. In the contact case, this subject is making nowadays its very first steps and is essentially unexplored. The progress in this direction will shed new light on the structure of these transformation groups playing a fundamental role in geometry, topology and dynamics."
Max ERC Funding
1 787 200 €
Duration
Start date: 2013-10-01, End date: 2019-09-30
Project acronym TORMCJ
Project Thermal, optical and redox processes in molecular conduction junctions
Researcher (PI) Abraham Nitzan
Host Institution (HI) TEL AVIV UNIVERSITY
Call Details Advanced Grant (AdG), PE4, ERC-2008-AdG
Summary Much of the current intense study of molecular conduction junctions is motivated by their possible technological applications, however this research focuses on fundamental questions associated with the properties and operation of such systems. Junctions based on redox molecules often show non-linear conduction behavior as function of imposed bias. Optical interactions in molecular junctions pertain to junction characterization and control. Issues of heating and thermal stability require a proper definition of thermal states (effective temperature) and the understanding of heat production and thermal conduction in non-equilibrium junctions. This proposal focuses on theoretical problems pertaining to these phenomena with the following goals: (a) Develop theoretical methodologies for treating non-equilibrium molecular systems under the combined driving of electrical bias, thermal gradients and optical fields; (b) provide theoretical tools needed for the understanding and interpretation of new and ongoing experimental efforts involving thermal, optical and redox (charging) phenomena in molecular junctions, and (c) use the acquired insight to suggest new methods for characterization, functionality, control and stability of molecular junctions.
Summary
Much of the current intense study of molecular conduction junctions is motivated by their possible technological applications, however this research focuses on fundamental questions associated with the properties and operation of such systems. Junctions based on redox molecules often show non-linear conduction behavior as function of imposed bias. Optical interactions in molecular junctions pertain to junction characterization and control. Issues of heating and thermal stability require a proper definition of thermal states (effective temperature) and the understanding of heat production and thermal conduction in non-equilibrium junctions. This proposal focuses on theoretical problems pertaining to these phenomena with the following goals: (a) Develop theoretical methodologies for treating non-equilibrium molecular systems under the combined driving of electrical bias, thermal gradients and optical fields; (b) provide theoretical tools needed for the understanding and interpretation of new and ongoing experimental efforts involving thermal, optical and redox (charging) phenomena in molecular junctions, and (c) use the acquired insight to suggest new methods for characterization, functionality, control and stability of molecular junctions.
Max ERC Funding
842 420 €
Duration
Start date: 2008-12-01, End date: 2014-05-31
