Displaying 1 - 29 of 29. Show 10 | 20 results per page.
Project acronym ARITHQUANTUMCHAOS
Project Arithmetic and Quantum Chaos
Researcher (PI) Zeev Rudnick
Host Institution (HI) TEL AVIV UNIVERSITY
Summary Quantum Chaos is an emerging discipline which is crossing over from Physics into Pure Mathematics. The recent crossover is driven in part by a connection with Number Theory. This project explores several aspects of this interrelationship and is composed of a number of sub-projects. The sub-projects deal with: statistics of energy levels and wave functions of pseudo-integrable systems, a hitherto unexplored subject in the mathematical community which is not well understood in the physics community; with statistics of zeros of zeta functions over function fields, a purely number theoretic topic which is linked to the subproject on Quantum Chaos through the mysterious connections to Random Matrix Theory and an analogy between energy levels and zeta zeros; and with spatial statistics in arithmetic.
Quantum Chaos is an emerging discipline which is crossing over from Physics into Pure Mathematics. The recent crossover is driven in part by a connection with Number Theory. This project explores several aspects of this interrelationship and is composed of a number of sub-projects. The sub-projects deal with: statistics of energy levels and wave functions of pseudo-integrable systems, a hitherto unexplored subject in the mathematical community which is not well understood in the physics community; with statistics of zeros of zeta functions over function fields, a purely number theoretic topic which is linked to the subproject on Quantum Chaos through the mysterious connections to Random Matrix Theory and an analogy between energy levels and zeta zeros; and with spatial statistics in arithmetic.
Project acronym DEPENDENTCLASSES
Project Model theory and its applications: dependent classes
Researcher (PI) Saharon Shelah
Summary Model theory deals with general classes of structures (called models). Specific examples of such classes are: the class of rings or the class of algebraically closed fields. It turns out that counting the so-called complete types over models in the class has an important role in the development of model theory in general and stability theory in particular. Stable classes are those with relatively few complete types (over structures from the class); understanding stable classes has been central in model theory and its applications. Recently, I have proved a new dichotomy among the unstable classes: Instead of counting all the complete types, they are counted up to conjugacy. Classes which have few types up to conjugacy are proved to be so-called ``dependent'' classes (which have also been called NIP classes). I have developed (under reasonable restrictions) a ``recounting theorem'', parallel to the basic theorems of stability theory. I have started to develop some of the basic properties of this new approach. The goal of the current project is to develop systematically the theory of dependent classes. The above mentioned results give strong indication that this new theory can be eventually as useful as the (by now the classical) stability theory. In particular, it covers many well known classes which stability theory cannot treat.
Model theory deals with general classes of structures (called models). Specific examples of such classes are: the class of rings or the class of algebraically closed fields. It turns out that counting the so-called complete types over models in the class has an important role in the development of model theory in general and stability theory in particular. Stable classes are those with relatively few complete types (over structures from the class); understanding stable classes has been central in model theory and its applications. Recently, I have proved a new dichotomy among the unstable classes: Instead of counting all the complete types, they are counted up to conjugacy. Classes which have few types up to conjugacy are proved to be so-called ``dependent'' classes (which have also been called NIP classes). I have developed (under reasonable restrictions) a ``recounting theorem'', parallel to the basic theorems of stability theory. I have started to develop some of the basic properties of this new approach. The goal of the current project is to develop systematically the theory of dependent classes. The above mentioned results give strong indication that this new theory can be eventually as useful as the (by now the classical) stability theory. In particular, it covers many well known classes which stability theory cannot treat.
Project acronym DISCONV
Project DISCRETE AND CONVEX GEOMETRY: CHALLENGES, METHODS, APPLICATIONS
Researcher (PI) Imre Barany
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Summary Title: Discrete and convex geometry: challenges, methods, applications Abstract: Research in discrete and convex geometry, using tools from combinatorics, algebraic topology, probability theory, number theory, and algebra, with applications in theoretical computer science, integer programming, and operations research. Algorithmic aspects are emphasized and often serve as motivation or simply dictate the questions. The proposed problems can be grouped into three main areas: (1) Geometric transversal, selection, and incidence problems, including algorithmic complexity of Tverberg's theorem, weak epsilon-nets, the k-set problem, and algebraic approaches to the Erdos unit distance problem. (2) Topological methods and questions, in particular topological Tverberg-type theorems, algorithmic complexity of the existence of equivariant maps, mass partition problems, and the generalized HeX lemma for the k-coloured d-dimensional grid. (3) Lattice polytopes and random polytopes, including Arnold's question on the number of convex lattice polytopes, limit shapes of lattice polytopes in dimension 3 and higher, comparison of random polytopes and lattice polytopes, the integer convex hull and its randomized version.
Title: Discrete and convex geometry: challenges, methods, applications Abstract: Research in discrete and convex geometry, using tools from combinatorics, algebraic topology, probability theory, number theory, and algebra, with applications in theoretical computer science, integer programming, and operations research. Algorithmic aspects are emphasized and often serve as motivation or simply dictate the questions. The proposed problems can be grouped into three main areas: (1) Geometric transversal, selection, and incidence problems, including algorithmic complexity of Tverberg's theorem, weak epsilon-nets, the k-set problem, and algebraic approaches to the Erdos unit distance problem. (2) Topological methods and questions, in particular topological Tverberg-type theorems, algorithmic complexity of the existence of equivariant maps, mass partition problems, and the generalized HeX lemma for the k-coloured d-dimensional grid. (3) Lattice polytopes and random polytopes, including Arnold's question on the number of convex lattice polytopes, limit shapes of lattice polytopes in dimension 3 and higher, comparison of random polytopes and lattice polytopes, the integer convex hull and its randomized version.
Project acronym DISCRETECONT
Project From discrete to contimuous: understanding discrete structures through continuous approximation
Researcher (PI) László Lovász
Host Institution (HI) EOTVOS LORAND TUDOMANYEGYETEM
Summary Important methods and results in discrete mathematics arise from the interaction between discrete mathematics and ``continuous'' areas like analysis or geometry. Classical examples of this include topological methods, linear and semidefinite optimization generating functions and more. More recent areas stressing this connection are the theory of limit objects of growing sequences of finite structures (graphs, hypergraphs, sequences), differential equations on networks, geometric representations of graphs. Perhaps most promising is the study of limits of growing graph and hypergraph sequences. In resent work by the Proposer and his collaborators, this area has found highly nontrivial connections with extremal graph theory, the theory of property testing in computer science, to additive number theory, the theory of random graphs, and measure theory as well as geometric representations of graphs. This proposal's goal is to explore these interactions, with the participation of a number of researchers from different areas of mathematics.
Important methods and results in discrete mathematics arise from the interaction between discrete mathematics and ``continuous'' areas like analysis or geometry. Classical examples of this include topological methods, linear and semidefinite optimization generating functions and more. More recent areas stressing this connection are the theory of limit objects of growing sequences of finite structures (graphs, hypergraphs, sequences), differential equations on networks, geometric representations of graphs. Perhaps most promising is the study of limits of growing graph and hypergraph sequences. In resent work by the Proposer and his collaborators, this area has found highly nontrivial connections with extremal graph theory, the theory of property testing in computer science, to additive number theory, the theory of random graphs, and measure theory as well as geometric representations of graphs. This proposal's goal is to explore these interactions, with the participation of a number of researchers from different areas of mathematics.
Project acronym DMMCA
Project Discrete Mathematics: methods, challenges and applications
Researcher (PI) Noga Alon
Summary Discrete Mathematics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. Some of the main reasons for this growth are the broad applications of tools and techniques from extremal and probabilistic combinatorics in the rapid development of theoretical Computer Science, in the spectacular recent results in Additive Number Theory and in the study of basic questions in Information Theory. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage, and often relies on deep, well developed tools, like the probabilistic method, algebraic, topological and geometric techniques. The work of the principal investigator, partly jointly with several collaborators and students, and partly in individual efforts, has played a significant role in the introduction of powerful algebraic, probabilistic, spectral and geometric techniques that influenced the development of modern combinatorics. In the present project he aims to try and further develop such tools, trying to tackle some basic open problems in Combinatorics, as well as significant questions in Additive Combinatorics, Information Theory, and theoretical Computer Science. Progress on the problems mentioned in this proposal, and the study of related ones, is expected to provide new insights on these problems and to lead to the development of novel fruitful techniques that are likely to be useful in Discrete Mathematics as well as in related areas.
Discrete Mathematics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. Some of the main reasons for this growth are the broad applications of tools and techniques from extremal and probabilistic combinatorics in the rapid development of theoretical Computer Science, in the spectacular recent results in Additive Number Theory and in the study of basic questions in Information Theory. While in the past many of the basic combinatorial results were obtained mainly by ingenuity and detailed reasoning, the modern theory has grown out of this early stage, and often relies on deep, well developed tools, like the probabilistic method, algebraic, topological and geometric techniques. The work of the principal investigator, partly jointly with several collaborators and students, and partly in individual efforts, has played a significant role in the introduction of powerful algebraic, probabilistic, spectral and geometric techniques that influenced the development of modern combinatorics. In the present project he aims to try and further develop such tools, trying to tackle some basic open problems in Combinatorics, as well as significant questions in Additive Combinatorics, Information Theory, and theoretical Computer Science. Progress on the problems mentioned in this proposal, and the study of related ones, is expected to provide new insights on these problems and to lead to the development of novel fruitful techniques that are likely to be useful in Discrete Mathematics as well as in related areas.
Project acronym EXPANDERS
Project Expander Graphs in Pure and Applied Mathematics
Researcher (PI) Alexander Lubotzky
Summary Expander graphs are finite graphs which play a fundamental role in many areas of computer science such as: communication networks, algorithms and more. Several areas of deep mathematics have been used in order to give explicit constructions of such graphs e.g. Kazhdan property (T) from representation theory of semisimple Lie groups, Ramanujan conjecture from the theory of automorphic forms and more. In recent years, computer science has started to pay its debt to mathematics: expander graphs are playing an increasing role in several areas of pure mathematics. The goal of the current research plan is to deepen these connections in both directions with special emphasis of the more recent and surprising application of expanders to group theory, the geometry of 3-manifolds and number theory.
Expander graphs are finite graphs which play a fundamental role in many areas of computer science such as: communication networks, algorithms and more. Several areas of deep mathematics have been used in order to give explicit constructions of such graphs e.g. Kazhdan property (T) from representation theory of semisimple Lie groups, Ramanujan conjecture from the theory of automorphic forms and more. In recent years, computer science has started to pay its debt to mathematics: expander graphs are playing an increasing role in several areas of pure mathematics. The goal of the current research plan is to deepen these connections in both directions with special emphasis of the more recent and surprising application of expanders to group theory, the geometry of 3-manifolds and number theory.
Project acronym GLC
Project Langlands correspondence and its variants
Researcher (PI) David Kazhdan
Summary Sometimes in the sciences there are different yet complementary descriptions for the same object. This extends to the particle-wave duality of quantum mechanics; one mathematical analog of this duality is the Fourier transform. Questions that are difficult when formulated in one language of science may become simple when interpreted in another. The Langlands conjecture posits the existence of a correspondence between problems in arithmetic and in Representation Theory. The Langlands conjecture has only been proven for a limited number of cases, but even this has solved problems such as the famous Fermat conjecture. The aim of this project is to continue study of the "classical" aspects of the Langlands conjecture and to extend the conjecture to the quantum geometric Langlands correspondence, higher-dimensional fields, Kac-Moody groups (with D.Gaitsgory: quantum Langlands correspondence; D.Gaitsgory and E. Hrushevsi: groups over higher-dimensional fields; A. Braverman: Kac-Moody groups; R. Bezrukavnikov, S.Debacker, Y.Varshavsky: classical aspects of the correspondence; A. Berenstein: geometric crystals and crystal bases). The quantum case is much more symmetric than the classical case and can lead in the limit q->0 to new insights into the classical case. The quantum case is also related to the multiple Dirichlet series. New results in the quantum case would lead to progress in understanding important Number Theoretic questions. Extending the Langlands correspondence to groups over higher-dimensional fields could substantially enlarge its applicability. Studying Kac-Moody groups would provide tools for the new important class of L-functions. This progress could lead to a proof of the existence of the analytic continuation of classical L-functions. The geometric Langlands correspondence is closely related to T-symmetry in 4-dimensional gauge theory and the understanding of this relation is important for both Mathematics and Physics.
Sometimes in the sciences there are different yet complementary descriptions for the same object. This extends to the particle-wave duality of quantum mechanics; one mathematical analog of this duality is the Fourier transform. Questions that are difficult when formulated in one language of science may become simple when interpreted in another. The Langlands conjecture posits the existence of a correspondence between problems in arithmetic and in Representation Theory. The Langlands conjecture has only been proven for a limited number of cases, but even this has solved problems such as the famous Fermat conjecture. The aim of this project is to continue study of the "classical" aspects of the Langlands conjecture and to extend the conjecture to the quantum geometric Langlands correspondence, higher-dimensional fields, Kac-Moody groups (with D.Gaitsgory: quantum Langlands correspondence; D.Gaitsgory and E. Hrushevsi: groups over higher-dimensional fields; A. Braverman: Kac-Moody groups; R. Bezrukavnikov, S.Debacker, Y.Varshavsky: classical aspects of the correspondence; A. Berenstein: geometric crystals and crystal bases). The quantum case is much more symmetric than the classical case and can lead in the limit q->0 to new insights into the classical case. The quantum case is also related to the multiple Dirichlet series. New results in the quantum case would lead to progress in understanding important Number Theoretic questions. Extending the Langlands correspondence to groups over higher-dimensional fields could substantially enlarge its applicability. Studying Kac-Moody groups would provide tools for the new important class of L-functions. This progress could lead to a proof of the existence of the analytic continuation of classical L-functions. The geometric Langlands correspondence is closely related to T-symmetry in 4-dimensional gauge theory and the understanding of this relation is important for both Mathematics and Physics.
Project acronym GMODGAMMADYNAMICS
Project Dynamics on homogeneous spaces, spectra and arithmetic
Researcher (PI) Elon Lindenstrauss
Summary We consider the dynamics of actions on homogeneous spaces of algebraic groups, We propose to tackle the central open problems in the area, including understanding actions of diagonal groups on homogeneous spaces without an entropy assumption, a related conjecture of Furstenberg about measures on R / Z invariant under multiplication by 2 and 3, and obtaining a quantitative understanding of equidistribution properties of unipotent flows and groups generated by unipotents. This has applications in arithmetic, Diophantine approximations, the spectral theory of homogeneous spaces, mathematical physics, and other fields. Connections to arithmetic combinatorics will be pursued.
We consider the dynamics of actions on homogeneous spaces of algebraic groups, We propose to tackle the central open problems in the area, including understanding actions of diagonal groups on homogeneous spaces without an entropy assumption, a related conjecture of Furstenberg about measures on R / Z invariant under multiplication by 2 and 3, and obtaining a quantitative understanding of equidistribution properties of unipotent flows and groups generated by unipotents. This has applications in arithmetic, Diophantine approximations, the spectral theory of homogeneous spaces, mathematical physics, and other fields. Connections to arithmetic combinatorics will be pursued.
Project acronym GROGandGIN
Project Growth in Groups and Graph Isomorphism Now
Researcher (PI) Laszlo Pyber
Summary "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."
"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."
Project acronym HAS
Project Harmonic Analysis and l-adic sheaves
Summary "In recent years there has been impressive development of the higher category theory and in particular development of the categorical counterpart of the Langlands conjecture over fields of finite characteristic. But until now, this development has had little bearing on the classical problems which deal with spaces of functions. The main goal of this proposal is to build the technique to apply the category theory to classical problems. Of course on the way I will have to deal with problems in the categorical realm. The first part of the proposal deals with construction of characters of irreducible representations of reductive groups over local nonarchimedian fields F in terms of traces of the Frobenious endomorphisms which should lead to the proof of the ""Stable center conjecture"" at least for representations of depth zero. The second part is on the extension of the definition of L-functions of representations of reductive F-groups corresponding to an arbitrary representation of the dual groups. As it is now, the definition is known only for very special representations of the dual group and only in the case of classical groups. The third part is on the extension of the classical theory to representations of Kac-Moody groups over local fields."
"In recent years there has been impressive development of the higher category theory and in particular development of the categorical counterpart of the Langlands conjecture over fields of finite characteristic. But until now, this development has had little bearing on the classical problems which deal with spaces of functions. The main goal of this proposal is to build the technique to apply the category theory to classical problems. Of course on the way I will have to deal with problems in the categorical realm. The first part of the proposal deals with construction of characters of irreducible representations of reductive groups over local nonarchimedian fields F in terms of traces of the Frobenious endomorphisms which should lead to the proof of the ""Stable center conjecture"" at least for representations of depth zero. The second part is on the extension of the definition of L-functions of representations of reductive F-groups corresponding to an arbitrary representation of the dual groups. As it is now, the definition is known only for very special representations of the dual group and only in the case of classical groups. The third part is on the extension of the classical theory to representations of Kac-Moody groups over local fields."
Project acronym HI-DIM COMBINATORICS
Project High-dimensional combinatorics
Researcher (PI) Nathan Linial
Summary This research program originates from a pressing practical need and from a purely new geometric perspective of discrete mathematics.. Graphs play a key role in many application areas of mathematics, providing the perfect mathematical description of all systems that are governed by pairwise interactions, in computer science, economics, biology and more. But graphs cannot fully capture scenarios in which interactions involve more than two agents. Since the theory of hypergraphs is still too under-developed, we resort to geometry and topology, which view a graph as a one-dimensional simplicial complex. I want to develop a combinatorial/geometric/probabilistic theory of higher-dimensional simplicial complexes. Inspired by the great success of random graph theory and its impact on discrete mathematics both theoretical and applied, I intend to develop a theory of random simplicial complexes. This combinatorial/geometric point of view and the novel high-dimensional perspective, shed new light on many fundamental combinatorial objects such as permutations, cycles and trees. We show that they all have high-dimensional analogs whose study leads to new deep mathematical problems. This holds a great promise for real-world applications, in view of the prevalence of such objects in application domains. Even basic aspects of graphs, permutations etc. are much more sophisticated and subtle in high dimensions. E.g., it is a key result that randomly evolving graphs undergo a phase transition and a sudden emergence of a giant component. Computer simulations of the evolution of higher-dimensional simplicial complexes, reveal an even more dramatic phase transition. Yet, we still do not even know what is a higher-dimensional giant component. I also show how to use simplicial complexes (deterministic and random) to construct better error-correcting codes. I suggest a new conceptual approach to the search for high-dimensional expanders, a goal sought by many renowned mathematicians.
This research program originates from a pressing practical need and from a purely new geometric perspective of discrete mathematics.. Graphs play a key role in many application areas of mathematics, providing the perfect mathematical description of all systems that are governed by pairwise interactions, in computer science, economics, biology and more. But graphs cannot fully capture scenarios in which interactions involve more than two agents. Since the theory of hypergraphs is still too under-developed, we resort to geometry and topology, which view a graph as a one-dimensional simplicial complex. I want to develop a combinatorial/geometric/probabilistic theory of higher-dimensional simplicial complexes. Inspired by the great success of random graph theory and its impact on discrete mathematics both theoretical and applied, I intend to develop a theory of random simplicial complexes. This combinatorial/geometric point of view and the novel high-dimensional perspective, shed new light on many fundamental combinatorial objects such as permutations, cycles and trees. We show that they all have high-dimensional analogs whose study leads to new deep mathematical problems. This holds a great promise for real-world applications, in view of the prevalence of such objects in application domains. Even basic aspects of graphs, permutations etc. are much more sophisticated and subtle in high dimensions. E.g., it is a key result that randomly evolving graphs undergo a phase transition and a sudden emergence of a giant component. Computer simulations of the evolution of higher-dimensional simplicial complexes, reveal an even more dramatic phase transition. Yet, we still do not even know what is a higher-dimensional giant component. I also show how to use simplicial complexes (deterministic and random) to construct better error-correcting codes. I suggest a new conceptual approach to the search for high-dimensional expanders, a goal sought by many renowned mathematicians.
Project acronym HIEXP
Project High Dimensional Expanders, Ramanujan Complexes and Codes
Researcher (PI) Alex LUBOTZKY
Summary "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."
"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."
Project acronym HomDyn
Project Homogenous dynamics, arithmetic and equidistribution
Summary We consider the dynamics of actions on homogeneous spaces of algebraic groups, and propose to tackle a wide range of problems in the area, including the central open problems. One main focus in our proposal is the study of the intriguing and somewhat subtle rigidity properties of higher rank diagonal actions. We plan to develop new tools to study invariant measures for such actions, including the zero entropy case, and in particular Furstenberg's Conjecture about $\times 2,\times 3$-invariant measures on $\R / \Z$. A second main focus is on obtaining quantitative and effective equidistribution and density results for unipotent flows, with emphasis on obtaining results with a polynomial error term. One important ingredient in our study of both diagonalizable and unipotent actions is arithmetic combinatorics. Interconnections between these subjects and arithmetic equidistribution properties, Diophantine approximations and automorphic forms will be pursued.
We consider the dynamics of actions on homogeneous spaces of algebraic groups, and propose to tackle a wide range of problems in the area, including the central open problems. One main focus in our proposal is the study of the intriguing and somewhat subtle rigidity properties of higher rank diagonal actions. We plan to develop new tools to study invariant measures for such actions, including the zero entropy case, and in particular Furstenberg's Conjecture about $\times 2,\times 3$-invariant measures on $\R / \Z$. A second main focus is on obtaining quantitative and effective equidistribution and density results for unipotent flows, with emphasis on obtaining results with a polynomial error term. One important ingredient in our study of both diagonalizable and unipotent actions is arithmetic combinatorics. Interconnections between these subjects and arithmetic equidistribution properties, Diophantine approximations and automorphic forms will be pursued.
Project acronym LogCorrelatedFields
Project Extremes in logarithmically correlated fields
Researcher (PI) Ofer Zeitouni
Summary 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.
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.
Project acronym LTDBud
Project Low Dimensional Topology in Budapest
Researcher (PI) Andras Istvan Stipsicz
Summary "Heegaard Floer theory. In this project (in collaboration with P. Ozsváth and Z. Szabó) we plan to extend our earlier results computing various versions of Heegaard Floer homologies purely combinatorially. We also plan to find combinatorial definitions of these invariants (as graded groups). Such results will potentially lead to a combinatorial description of 4-dimensional Heegaard Floer (mixed) invariants, conjecturally equivalent to Seiberg-Witten invariants of smooth 4-manifolds. In particular, we hope to find a combinatorial proof of Donaldson's diagonalizability theorem, and find relations between the Heegaard Floer and the fundamental groups of a 3-manifold. Contact topology. Using Heegaard Floer theory and contact surgery, a systematic study of existence of tight contact structures on 3-manifolds is planned. Similar techniques also apply in studying Legendrian and transverse knots in contact 3-manifolds. In particular, the verification of the existence of tight structures on 3-manifolds given by surgery on a knot (with high enough framing) in the 3-sphere is proposed. Using the Legendrian invariant of knots, Legendrian and transverse simplicity can be conveniently studied. The ideas detailed in this part are planned to be carried out partly in collaboration with Paolo Lisca, Vera Vértesi and Hansjörg Geiges. Exotic 4-manifolds. Extending our previous results, we plan to investigate the existence of exotic smooth structures on 4-manifolds with small Euler characteristics, such as the complex projective plane CP2, its blow-up CP2#CP2-bar, the product of two complex projective lines CP1×CP1 and ultimately the 4-dimensional sphere S4. We plan to investigate the effect of the Gluck transformation. Possible extensions of the rational blow down procedure (successful in producing exotic structures) will be also studied. We plan collaborations with Zoltán Szabó, Daniel Nash and Mohan Bhupal in these questions."
"Heegaard Floer theory. In this project (in collaboration with P. Ozsváth and Z. Szabó) we plan to extend our earlier results computing various versions of Heegaard Floer homologies purely combinatorially. We also plan to find combinatorial definitions of these invariants (as graded groups). Such results will potentially lead to a combinatorial description of 4-dimensional Heegaard Floer (mixed) invariants, conjecturally equivalent to Seiberg-Witten invariants of smooth 4-manifolds. In particular, we hope to find a combinatorial proof of Donaldson's diagonalizability theorem, and find relations between the Heegaard Floer and the fundamental groups of a 3-manifold. Contact topology. Using Heegaard Floer theory and contact surgery, a systematic study of existence of tight contact structures on 3-manifolds is planned. Similar techniques also apply in studying Legendrian and transverse knots in contact 3-manifolds. In particular, the verification of the existence of tight structures on 3-manifolds given by surgery on a knot (with high enough framing) in the 3-sphere is proposed. Using the Legendrian invariant of knots, Legendrian and transverse simplicity can be conveniently studied. The ideas detailed in this part are planned to be carried out partly in collaboration with Paolo Lisca, Vera Vértesi and Hansjörg Geiges. Exotic 4-manifolds. Extending our previous results, we plan to investigate the existence of exotic smooth structures on 4-manifolds with small Euler characteristics, such as the complex projective plane CP2, its blow-up CP2#CP2-bar, the product of two complex projective lines CP1×CP1 and ultimately the 4-dimensional sphere S4. We plan to investigate the effect of the Gluck transformation. Possible extensions of the rational blow down procedure (successful in producing exotic structures) will be also studied. We plan collaborations with Zoltán Szabó, Daniel Nash and Mohan Bhupal in these questions."
Project acronym METSTEM
Project DNA methylation in stem cells
Researcher (PI) Howard Cedar
Summary Embryonic and adult stem cells constitute an important component of biology by providing a pool of pluri- and multi-potent cells that supply a variety of different cell lineages. Little is known about the mechanisms involved in establishing and maintaining cell ¿stemness,¿ but it is most likely controlled by epigenetic signals such as DNA methylation. This proposal aims to understand these mechanisms and decipher the molecular logic used to program this plasticity. We have developed a new strategy for studying the ¿DNA methylation potential¿ of any cell type throughout normal development. This utilizes a unique set of transgenic vectors programmed to detect both de novo methylation as well as the ability to protect CpG islands, and will, for the first time, allow one to evaluate the role of demethylation in normal stem cells and during reprogramming. This will be done using a new technique called ¿reverse epigenetics¿. Preliminary studies indicate that embryonic stem cells differentiated in vitro undergo extensive aberrant methylation that does not reflect the normal pattern of methylation found in vivo. This artifact may be responsible for our inability to attain efficient differentiation in culture and may generate cells that are unhealthy and prone to cancer. We will characterize the causes of this phenomenon and decipher its underlying mechanism. This research should lead to the development of improved methods for tissue generation in vitro. One of the most basic properties of adult stem cells is their ability to undergo asymmetric cell division that is often associated with unequal segregation of DNA. This mechanism is one of the most elemental, yet mysterious, aspects of stem cell biology. We have developed a completely new molecular model for this process that is based on the idea that non-symmetric DNA methylation serves as a strand-specific marker, and it is very likely that this will enable us to finally decipher this basic aspect of stem cells.
Embryonic and adult stem cells constitute an important component of biology by providing a pool of pluri- and multi-potent cells that supply a variety of different cell lineages. Little is known about the mechanisms involved in establishing and maintaining cell ¿stemness,¿ but it is most likely controlled by epigenetic signals such as DNA methylation. This proposal aims to understand these mechanisms and decipher the molecular logic used to program this plasticity. We have developed a new strategy for studying the ¿DNA methylation potential¿ of any cell type throughout normal development. This utilizes a unique set of transgenic vectors programmed to detect both de novo methylation as well as the ability to protect CpG islands, and will, for the first time, allow one to evaluate the role of demethylation in normal stem cells and during reprogramming. This will be done using a new technique called ¿reverse epigenetics¿. Preliminary studies indicate that embryonic stem cells differentiated in vitro undergo extensive aberrant methylation that does not reflect the normal pattern of methylation found in vivo. This artifact may be responsible for our inability to attain efficient differentiation in culture and may generate cells that are unhealthy and prone to cancer. We will characterize the causes of this phenomenon and decipher its underlying mechanism. This research should lead to the development of improved methods for tissue generation in vitro. One of the most basic properties of adult stem cells is their ability to undergo asymmetric cell division that is often associated with unequal segregation of DNA. This mechanism is one of the most elemental, yet mysterious, aspects of stem cell biology. We have developed a completely new molecular model for this process that is based on the idea that non-symmetric DNA methylation serves as a strand-specific marker, and it is very likely that this will enable us to finally decipher this basic aspect of stem cells.
Project acronym MODAG
Project Model Theory and asymptotic geometry
Researcher (PI) Ehud Hrushovski
Summary The principal methods of model theory, in its connections to algebraic geometry, have been quantifier elimination (e.g. Tarski's theorem) and structural stability (used here in a wide sense, including simplicity, NIP and structural o-minimality.) We propose to move beyond current limitations on both fronts, by means of three interrelated projects. (1) A study of definable sets in global fields. A successful quantifier elimination result in this setting would extend the reach of model theory to wide areas of number theory and geometry that have not been accessible before, including points of small height in number theory, and the Gromov-Witten invariants of a variety in geometry. (2) A study of limits of o-minimal metric structures as quotients of non-archimedean structures, extending similar measure and group-theoretic work that has led to a resolution of Pillay's conjectures in the o-minimal setting, and leading towards a model theory of Calabi-Yau degenerations. (3) Model theoretic asymptotic limits lead to measure and dimension theories, with associated dependence theories, that resemble known structures from stability theory but do not lie within the stable realm or its current extensions. Preliminary stability-theoretic considerations have already led to significant applications in combinatorics. We propose creating a structural stability theory based on pseudo-finite dimension, expected to create a long-term bridge between model theory and additive combinatorics.
The principal methods of model theory, in its connections to algebraic geometry, have been quantifier elimination (e.g. Tarski's theorem) and structural stability (used here in a wide sense, including simplicity, NIP and structural o-minimality.) We propose to move beyond current limitations on both fronts, by means of three interrelated projects. (1) A study of definable sets in global fields. A successful quantifier elimination result in this setting would extend the reach of model theory to wide areas of number theory and geometry that have not been accessible before, including points of small height in number theory, and the Gromov-Witten invariants of a variety in geometry. (2) A study of limits of o-minimal metric structures as quotients of non-archimedean structures, extending similar measure and group-theoretic work that has led to a resolution of Pillay's conjectures in the o-minimal setting, and leading towards a model theory of Calabi-Yau degenerations. (3) Model theoretic asymptotic limits lead to measure and dimension theories, with associated dependence theories, that resemble known structures from stability theory but do not lie within the stable realm or its current extensions. Preliminary stability-theoretic considerations have already led to significant applications in combinatorics. We propose creating a structural stability theory based on pseudo-finite dimension, expected to create a long-term bridge between model theory and additive combinatorics.
Project acronym NOVRIB
Project Novel Insights into Multi-drug Resistance to Antibiotics and the Primordial Ribosome
Researcher (PI) Ada Yonath
Summary Multi-drug resistant phenotype formation creates global severe clinical threat among the most important challenges facing medicine today, dictating an urgent need for novel approaches. We aim to reveal the scope and mechanisms of resistance in pathogens, by studies that have not been pursued so far worldwide. In parallel we initiated innovative research towards understanding the ribosome origin, aiming at illuminating the transition from the primordial RNA world to the contemporary coded translation era, alongside exploring new targets and providing useful clues for antibiotics design. We base our interdisciplinary objectives on our discoveries originating from the ribosomes high resolution structures, the results of our pioneering efforts and subsequent perseverance. By revealing unique properties of genuine pathogens that facilitate their exclusive resistance pathways,instead of depending solely on benign eubacterial models, we expect to gain matchless new insights. As no crystals of ribosomes from pathogens are available, we have initiated crystallographic studies, and present here preliminary results on two pathogenic life threatening bacteria, Staphylococcus aureus (associated with MRSA resistance) and Mycobacterium tuberculosis via Mycobacterium smegmatis that serve as its medical diagnostic tool. We also aim at experimentally defining the intra-ribosome region suggested by us to be a vestige of a prebiotic apparatus (proto-ribosome) by designing autonomous molecular entities with catalytic capabilities. Constructs the bind substrates have already been obtained. The expected enhancement in understanding peptide bond formation should lead to novel insights into this universal essential process. Our studies are designed to provide unprecedentedly powerful new tools for minimizing pathogens resistance thus should be of immense therapeutic relevance & will open up new horizons for researchers seeking response to challenges of the increasing antibiotic resistance.
Multi-drug resistant phenotype formation creates global severe clinical threat among the most important challenges facing medicine today, dictating an urgent need for novel approaches. We aim to reveal the scope and mechanisms of resistance in pathogens, by studies that have not been pursued so far worldwide. In parallel we initiated innovative research towards understanding the ribosome origin, aiming at illuminating the transition from the primordial RNA world to the contemporary coded translation era, alongside exploring new targets and providing useful clues for antibiotics design. We base our interdisciplinary objectives on our discoveries originating from the ribosomes high resolution structures, the results of our pioneering efforts and subsequent perseverance. By revealing unique properties of genuine pathogens that facilitate their exclusive resistance pathways,instead of depending solely on benign eubacterial models, we expect to gain matchless new insights. As no crystals of ribosomes from pathogens are available, we have initiated crystallographic studies, and present here preliminary results on two pathogenic life threatening bacteria, Staphylococcus aureus (associated with MRSA resistance) and Mycobacterium tuberculosis via Mycobacterium smegmatis that serve as its medical diagnostic tool. We also aim at experimentally defining the intra-ribosome region suggested by us to be a vestige of a prebiotic apparatus (proto-ribosome) by designing autonomous molecular entities with catalytic capabilities. Constructs the bind substrates have already been obtained. The expected enhancement in understanding peptide bond formation should lead to novel insights into this universal essential process. Our studies are designed to provide unprecedentedly powerful new tools for minimizing pathogens resistance thus should be of immense therapeutic relevance & will open up new horizons for researchers seeking response to challenges of the increasing antibiotic resistance.
Project acronym POTENTIALTHEORY
Project Potential theoretic methods in approximation and orthogonal polynomials
Researcher (PI) Vilmos Totik
Host Institution (HI) SZEGEDI TUDOMANYEGYETEM
Summary The project is aimed at systematic applications of potential theoretical methods in approximation theory and in the theory of orthogonal polynomials. Various open problems are proposed in different fields which can be attacked with tools that have been developed in the near past or are to be developed within the project. The main areas are asymptotic behavior of Christoffel functions on the real line and on curves, the universality problem in random matrices, orthogonal polynomials and their zeros, polynomial inequalities, approximation by homogeneous polynomials and some questions in numerical analysis. The research problems and areas discussed in the proposal are intensively investigated in current research. As has been the case in the past, PhD students will be actively involved in the project.
The project is aimed at systematic applications of potential theoretical methods in approximation theory and in the theory of orthogonal polynomials. Various open problems are proposed in different fields which can be attacked with tools that have been developed in the near past or are to be developed within the project. The main areas are asymptotic behavior of Christoffel functions on the real line and on curves, the universality problem in random matrices, orthogonal polynomials and their zeros, polynomial inequalities, approximation by homogeneous polynomials and some questions in numerical analysis. The research problems and areas discussed in the proposal are intensively investigated in current research. As has been the case in the past, PhD students will be actively involved in the project.
Project acronym PRIMEGAPS
Project Gaps between primes and almost primes. Patterns in primes and almost primes. Approximations to the twin prime and Goldbach conjectures
Researcher (PI) Janos Pintz
Summary The twin prime conjecture, that n and n+2 are infinitely often primes simultaneously, is probably the oldest unsolved problem in mathematics. De Polignac (1849) conjectured that for every even value of h, n and n+h are infinitely often primes simultaneously. These are the most basic problems on gaps and patterns in primes. Another one is the conjecture of Waring (1770), stating that there are arbitrarily long arithmetic progressions (AP) of primes. For the newest developments we cite Granville (Bull. AMS 43 (2006), p.93): ): Despite much research of excellent quality, there have been few breakthroughs on the most natural questions about the distribution of prime numbers in the last few decades. That situation has recently changed dramatically with two extraordinary breakthroughs, each on questions that the experts had held out little hope for in the foreseeable future. Green and Tao proved that there are infinitely many k-term arithmetic progressions of primes using methods that are mostly far removed from mainstream analytic number theory. Indeed, their work centers around a brilliant development of recent results in ergodic theory and harmonic analysis. Their proof is finished, in a natural way, by an adaptation of the proof of the other fantastic new result in this area, Goldston, Pintz and Yildirim s proof that there are small gaps between primes. The proposal's aim is to study these types of patterns in primes with possible combination of the two theories. We quote 3 of the main problems, the first one being the most important. 1) Bounded Gap Conjecture. Are there infinitely many bounded gaps between primes? 2) Suppose that primes have a level of distribution larger than 1/2. Does a fixed h exists such that for every k there is a k-term AP of generalised twin prime pairs (p, p+h)? 3) Erdôs' conjecture for k=3. Suppose A is a sequence of natural numbers, such that the sum of their reciprocals is unbounded. Does A contain infinitely many 3-term AP's?
The twin prime conjecture, that n and n+2 are infinitely often primes simultaneously, is probably the oldest unsolved problem in mathematics. De Polignac (1849) conjectured that for every even value of h, n and n+h are infinitely often primes simultaneously. These are the most basic problems on gaps and patterns in primes. Another one is the conjecture of Waring (1770), stating that there are arbitrarily long arithmetic progressions (AP) of primes. For the newest developments we cite Granville (Bull. AMS 43 (2006), p.93): ): Despite much research of excellent quality, there have been few breakthroughs on the most natural questions about the distribution of prime numbers in the last few decades. That situation has recently changed dramatically with two extraordinary breakthroughs, each on questions that the experts had held out little hope for in the foreseeable future. Green and Tao proved that there are infinitely many k-term arithmetic progressions of primes using methods that are mostly far removed from mainstream analytic number theory. Indeed, their work centers around a brilliant development of recent results in ergodic theory and harmonic analysis. Their proof is finished, in a natural way, by an adaptation of the proof of the other fantastic new result in this area, Goldston, Pintz and Yildirim s proof that there are small gaps between primes. The proposal's aim is to study these types of patterns in primes with possible combination of the two theories. We quote 3 of the main problems, the first one being the most important. 1) Bounded Gap Conjecture. Are there infinitely many bounded gaps between primes? 2) Suppose that primes have a level of distribution larger than 1/2. Does a fixed h exists such that for every k there is a k-term AP of generalised twin prime pairs (p, p+h)? 3) Erdôs' conjecture for k=3. Suppose A is a sequence of natural numbers, such that the sum of their reciprocals is unbounded. Does A contain infinitely many 3-term AP's?
Project acronym PROGEOCOM
Project Avenues in Probabilistic and Geometric Combinatorics
Researcher (PI) Gil Kalai
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.
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.
Project acronym RandomZeroSets
Project Zero sets of random functions
Researcher (PI) Mikhail SODIN
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."
"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."
Project acronym REGULARITY
Project Regularity and Irregularity in Combinatorics and Number Theory
Researcher (PI) Endre Szemeredi
Summary "Regularity and irregularity plays a central role in mathematics. In the present research proposal we will select problems from combinatorics and number theory (including additive combinatorics), where regularity and irregularity appear. In some cases we have to deal, e.g., with arbitrary finite or infinite subsets of natural numbers, where the only information we have is their cardinality, namely, that they are of positive (lower asymptotic) density within the set of all natural numbers or within the interval [1,N] for a large N. In other cases we consider an arbitrary distribution of n points within the unit square, where all we know is the density of our point set. The goal is often to show that certain configurations appear within the arbitrary set of numbers or points. These configurations definitely appear in a random set of numbers or points, but we have to show this for an arbitrary set of numbers or points with certain general properties. In order to reach our goal one can use two well-known methods. The first one is deterministic, often some kind of greedy algorithm. The second is the probabilistic method of Erdős, which shows that almost all arrangements of the given points or numbers (or graphs) fulfill the wanted property. A third method, the so called pseudorandom method, was initiated by the PI (together with M. Ajtai and J. Komlós), uses a combination of these. In other cases we have a deterministic set of numbers with certain quasi-random properties, for example, the primes. Randomness was the key idea in the recent breakthrough of Green and Tao, in proving that primes contain arbitrarily long arithmetic progressions. We will deal with 6 groups of problems: (i) finite or infinite sequences of integers, (ii) difference sets and Fourier analysis, (iii) graph and hypergraph embedding theorems, (iv) Ramsey theory, (v) distribution of points in the plane and in the unit square, (vi) regularities and irregularities in the distribution of primes."
"Regularity and irregularity plays a central role in mathematics. In the present research proposal we will select problems from combinatorics and number theory (including additive combinatorics), where regularity and irregularity appear. In some cases we have to deal, e.g., with arbitrary finite or infinite subsets of natural numbers, where the only information we have is their cardinality, namely, that they are of positive (lower asymptotic) density within the set of all natural numbers or within the interval [1,N] for a large N. In other cases we consider an arbitrary distribution of n points within the unit square, where all we know is the density of our point set. The goal is often to show that certain configurations appear within the arbitrary set of numbers or points. These configurations definitely appear in a random set of numbers or points, but we have to show this for an arbitrary set of numbers or points with certain general properties. In order to reach our goal one can use two well-known methods. The first one is deterministic, often some kind of greedy algorithm. The second is the probabilistic method of Erdős, which shows that almost all arrangements of the given points or numbers (or graphs) fulfill the wanted property. A third method, the so called pseudorandom method, was initiated by the PI (together with M. Ajtai and J. Komlós), uses a combination of these. In other cases we have a deterministic set of numbers with certain quasi-random properties, for example, the primes. Randomness was the key idea in the recent breakthrough of Green and Tao, in proving that primes contain arbitrarily long arithmetic progressions. We will deal with 6 groups of problems: (i) finite or infinite sequences of integers, (ii) difference sets and Fourier analysis, (iii) graph and hypergraph embedding theorems, (iv) Ramsey theory, (v) distribution of points in the plane and in the unit square, (vi) regularities and irregularities in the distribution of primes."
Project acronym RMAST
Project Random Models in Arithmetic and Spectral Theory
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.
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.
Project acronym SensStabComp
Project Sensitivity, Stability, and Computation
Host Institution (HI) INTERDISCIPLINARY CENTER (IDC) HERZLIYA
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.
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.
Project acronym STACKSRTFPERIODS
Project Stacks in Representation Theory, Relative Trace Formula and analysis of Automorphic Periods
Researcher (PI) Joseph Bernstein
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)."
"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)."
Project acronym SYMPTOPODYNQUANT
Project Symplectic topology and its interactions: from dynamics to quantization
Researcher (PI) Leonid Polterovich
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."
"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."
Project acronym URSAT
Project Understanding Random Systems via Algebraic Topology
Researcher (PI) Robert Joseph Adler
Summary Over the past decade there has been a significant expansion of activity in applying the techniques and theory of algebraic topology to real world problems. The expression `applied algebraic topology' is no longer an oxymoron! This expansion has generated new mathematical theory, new computational techniques, and even commercial startups. However, there is still an important component of this topological approach that has not been treated in any depth, and this is the inherently stochastic nature of the world. Consequently, there is an urgent need to complement recent developments, which have been primarily deterministic, with sophisticated stochastic modelling and analysis. The current proposal aims to attack this issue by applying algebraic topological thinking to random systems. Over the past two years, the PI Adler and colleagues have organised workshops in Banff, Palo Alto and Chicago with tens of researchers from topology, probability, statistics, random networks, image analysis and other areas, with the aim of defining the important problems that `random algebraic topology' should address. These brain trusts have born fruit in terms of setting some clearly defined goals, many of which help motivate the core of the current proposal, which is by far the most ambitious of a number of earlier and current projects. These endeavours are expected to have -- and are to a considerable part driven by -- applications to areas outside of mathematics, while at the same time having deep, intrinsic, mathematical interest. The multi-faceted aspect of the proposal, involving a number of areas within mathematics that do not usually appear together, is highly novel and requires the setting up of a large and coordinated team of researchers. This will include the PI, graduate students and postdoctoral fellows, and short and medium term visiting scholars from a variety of disciplines
Over the past decade there has been a significant expansion of activity in applying the techniques and theory of algebraic topology to real world problems. The expression `applied algebraic topology' is no longer an oxymoron! This expansion has generated new mathematical theory, new computational techniques, and even commercial startups. However, there is still an important component of this topological approach that has not been treated in any depth, and this is the inherently stochastic nature of the world. Consequently, there is an urgent need to complement recent developments, which have been primarily deterministic, with sophisticated stochastic modelling and analysis. The current proposal aims to attack this issue by applying algebraic topological thinking to random systems. Over the past two years, the PI Adler and colleagues have organised workshops in Banff, Palo Alto and Chicago with tens of researchers from topology, probability, statistics, random networks, image analysis and other areas, with the aim of defining the important problems that `random algebraic topology' should address. These brain trusts have born fruit in terms of setting some clearly defined goals, many of which help motivate the core of the current proposal, which is by far the most ambitious of a number of earlier and current projects. These endeavours are expected to have -- and are to a considerable part driven by -- applications to areas outside of mathematics, while at the same time having deep, intrinsic, mathematical interest. The multi-faceted aspect of the proposal, involving a number of areas within mathematics that do not usually appear together, is highly novel and requires the setting up of a large and coordinated team of researchers. This will include the PI, graduate students and postdoctoral fellows, and short and medium term visiting scholars from a variety of disciplines
Project acronym WORDS
Project Words and Waring type problems
Researcher (PI) Aner Shalev
Summary Hilbert's solution to Waring problem in Number Theory shows that every positive integer is a sum of g(n) nth powers. Surprising non-commutative analogues of this phenomenon were discovered recently in Group Theory, where powers are replaced by general words. Moreover, the study of group words occurs naturally in important contexts, such as the Burnside problems, Serre's problem on profinite groups, and finite simple group theory. We propose a systematic study of word maps on groups, their images and kernels, as well as related Waring type problems. These include a celebrated conjecture of Thompson, problems regarding covering numbers and mixing times of random walks, as well as probabilistic identities in finite and profinite groups. This is a highly challenging project in which we intend to utilize a wide spectrum of tools, including Representation Theory, Algebraic Geometry, Number Theory, computational group theory, as well as probabilistic methods and Lie methods. Moreover, we aim to establish new results on representations and character bounds, which would be very useful in various additional contexts. Apart from their intrinsic interest, the problems and conjectures we propose have exciting applications to other fields, and the project is likely to shed new light not just in group theory but also in combinatorics, probability and geometry.
Hilbert's solution to Waring problem in Number Theory shows that every positive integer is a sum of g(n) nth powers. Surprising non-commutative analogues of this phenomenon were discovered recently in Group Theory, where powers are replaced by general words. Moreover, the study of group words occurs naturally in important contexts, such as the Burnside problems, Serre's problem on profinite groups, and finite simple group theory. We propose a systematic study of word maps on groups, their images and kernels, as well as related Waring type problems. These include a celebrated conjecture of Thompson, problems regarding covering numbers and mixing times of random walks, as well as probabilistic identities in finite and profinite groups. This is a highly challenging project in which we intend to utilize a wide spectrum of tools, including Representation Theory, Algebraic Geometry, Number Theory, computational group theory, as well as probabilistic methods and Lie methods. Moreover, we aim to establish new results on representations and character bounds, which would be very useful in various additional contexts. Apart from their intrinsic interest, the problems and conjectures we propose have exciting applications to other fields, and the project is likely to shed new light not just in group theory but also in combinatorics, probability and geometry.