ERC FUNDED PROJECTS

The importance of understanding the functions of the basic building blocks of life, such as proteins, cannot be overstated (as asserted by two recent Nobel prizes in Chemistry), as this understanding unravels the mechanisms that control all organisms. The critical step towards such an understanding is to reveal the structures of these building blocks. A leading method for resolving such structures is cryo-electron microscopy (cryo-EM), in which the structure of a molecule is recovered from its images taken by an electron microscope, by using sophisticated mathematical algorithms (to which my group has made several key mathematical and algorithmic contributions). Due to hardware breakthroughs in the past three years, cryo-EM has made a giant leap forward, introducing capabilities that until recently were unimaginable, opening an opportunity to revolutionize our biological understanding. As extracting information from cryo-EM experiments completely relies on mathematical algorithms, the method’s deep mathematical challenges that have emerged must be solved as soon as possible. Only then cryo-EM could realize its nearly inconceivable potential. These challenges, for which no adequate solutions exist (or none at all), focus on integrating information from huge sets of extremely noisy images reliability and efficiently. Based on the experience of my research group in developing algorithms for cryo-EM data processing, gained during the past eight years, we will address the three key open challenges of the field – a) deriving reliable and robust reconstruction algorithms from cryo-EM data, b) developing tools to process heterogeneous cryo-EM data sets, and c) devising validation and quality measures for structures determined from cryo-EM data. The fourth goal of the project, which ties all goals together and promotes the broad interdisciplinary impact of the project, is to merge all our algorithms into a software platform for state-of-the-art processing of cryo-EM data.

1 751 250 €

Start date: 2017-03-01, End date: 2022-02-28

"In recent years there has been spectacular progress in studying growth in groups. A central result in this new area, obtained by Pyber-Szabo' (with a similar result proved by Breuillard-Green-Tao), shows that powers of generating subsets of finite simple groups of ""bounded dimension"" grow fast. Extending this Product Theorem Szabo' and the PI also proved a weaker version of a conjecture of Helfgott-Lindenstrauss. The Product Theorem has deep consequences in the study of groups, number theory and random walks. A central open question of the area is to remove the dependence on dimension in our Product Theorem. The PI formulated a new Conjecture, as a step forward. The way to further progress is via combining techniques from asymptotic group theory and probability theory. It is from this perspective that the current GROGandGIN proposal addresses issues concerning random walks. We examine how recent probabilistic arguments for random walks in the symmetric group may be transferred to matrix groups. While the first results in the subject of growth concern matrix groups we see an evolving theory of growth in permutation groups. This relies on earlier work of Babai and the PI which aims at finding proofs which do not use the Classification of Finite Simple Groups (CFSG). Similarly, Babai's famous Quasipolynomial Graph Isomorphism Algorithm builds on ideas from CFSG-free proofs due to him. The PI has recently removed CFSG from the analysis of Babai's algorithm. Our method goes ""halfway"" towards removing CFSG from proofs of growth results for permutation groups, currently a major open problem. The GROGandGIN initiative plans to improve various other parts of Babai's paper, working with several people who look at it from different angles, with an eye towards obtaining a Polynomial Graph Isomorphism algorithm. The GROGandGIN team will also study growth in Lie groups since the theory of random walks in Lie groups has been revitalised using analogues of our Product Theorem."

1 965 340 €

Start date: 2017-08-01, End date: 2022-07-31

"Expander graphs have been playing a fundamental role in many areas of computer science. During the last 15 years they have also found important and unexpected applications in pure mathematics. The goal of the current research is to develop systematically high-dimensional (HD) theory of expanders, i.e., simplicial complexes and hypergraphs which resemble in dimension d, the role of expander graphs for d = 1. There are several motivations for developing such a theory, some from pure mathematics and some from computer science. For example, Ramanujan complexes (the HD versions of the ""optimal"" expanders, the Ramanujan graphs) have already been useful for extremal hypergraph theory. One of the main goals of this research is to use them to solve other problems, such as Gromov's problem: are there bounded degree simplicial complexes with the topological overlapping property (""topological expanders""). Other directions of HD expanders have applications in property testing, a very important subject in theoretical computer science. Moreover they can be a tool for the construction of locally testable codes, an important question of theoretical and practical importance in the theory of error correcting codes. In addition, the study of these simplicial complexes suggests new quantum error correcting codes (QECC). It is hoped that it will lead to such codes which are also low density parity check (LDPC). The huge success and impact of the theory of expander graphs suggests that the high dimensional theory will also bring additional unexpected applications beside those which can be foreseen as of now."

1 592 500 €

Start date: 2016-08-01, End date: 2021-07-31

The proposed research deals with the extremes of logarithmically correlated fields, in both the Gaussian and non-Gaussian setups. Examples of such fields are branching random walks, the (discrete) two dimensional Gaussian free field, the set of points left uncovered by a random walk on the two dimensional torus at times close to the cover time of the torus, the (absolute) values of the characteristic polynomial of random matrices, Ginzburg-Landau models, and more. The proposal builds on recent progress in the study of the maximum and of the extremal process of the two dimensional Gaussian free field, which was made possible by Gaussian comparisons and the introduction of a refined version of the second moment method. The proposed research will develop the tools needed for building a general and flexible theory applicable to general logarithmically correlated fields. Applications to the multiplicative chaos will also be considered.

1 292 500 €

Start date: 2016-06-01, End date: 2021-12-31

The objective of this proposal is an investigation of the geometric structure of random spaces that arise in critical models of statistical physics. The proposal is motivated by inspiring yet non-rigorous predictions from the physics community and the models studied are some of the most popular models in contemporary probability theory such as percolation, random planar maps and random walks. One set of problems are on the topic of random planar maps and quantum gravity, a thriving field on the intersection of probability, statistical physics, combinatorics and complex analysis. Our goal is to develop a rigorous theory of these maps viewed as surfaces (rather than metric spaces) via their circle packing. The circle packing structure was recently used by the PI and Gurel-Gurevich to show that these maps are a.s. recurrent, resolving a major conjecture in this area. Among other consequences, this research will hopefully lead to progress on the most important open problem in this field: a rigorous proof of the mysterious KPZ correspondence, a conjectural formula from the physics literature allowing to compute dimensions of certain random sets in the usual square lattice from the corresponding dimension in the random geometry. Such a program will hopefully lead to the solution of the most central problems in two-dimensional statistical physics, such as finding the typical displacement of the self-avoiding walk, proving conformal invariance for percolation on the square lattice and many others. Another set of problems is investigating aspects of universality in critical percolation in various high-dimensional graphs. These graphs include lattices in dimension above 6, Cayley graphs of finitely generated non-amenable groups and also finite graphs such as the complete graph, the Hamming hypercube and expanders. It is believed that critical percolation on these graphs is universal in the sense that the resulting percolated clusters exhibit the same mean-field geometry.

1 286 150 €

Start date: 2016-01-01, End date: 2020-12-31