ERC FUNDED PROJECTS

In a typical learning problem one tries to approximate an unknown function by a function from a given class using random data, sampled according to an unknown measure. In this project we will be interested in parameters that govern the complexity of a learning problem. It turns out that this complexity is determined by the geometry of certain sets in high dimension that are connected to the given class (random coordinate projections of the class). Thus, one has to understand the structure of these sets as a function of the dimension - which is given by the cardinality of the random sample. The resulting analysis leads to many theoretical questions in Asymptotic Geometric Analysis, Probability (most notably, Empirical Processes Theory) and Combinatorics, which are of independent interest beyond the application to Learning Theory. Our main goal is to describe the role of various complexity parameters involved in a learning problem, to analyze the connections between them and to investigate the way they determine the geometry of the relevant high dimensional sets. Some of the questions we intend to tackle are well known open problems and making progress towards their solution will have a significant theoretical impact. Moreover, this project should lead to a more complete theory of learning and is likely to have some practical impact, for example, in the design of more efficient learning algorithms.

750 000 €

Start date: 2009-03-01, End date: 2014-02-28

We propose to establish a research group that will unveil the combinatorial nature of the second uncountable cardinal. This includes its Ramsey-theoretic, order-theoretic, graph-theoretic and topological features. Among others, we will be directly addressing fundamental problems due to Erdos, Rado, Galvin, and Shelah. While some of these problems are old and well-known, an unexpected series of breakthroughs from the last three years suggest that now is a promising point in time to carry out such a project. Indeed, through a short period, four previously unattainable problems concerning the second uncountable cardinal were successfully tackled: Aspero on a club-guessing problem of Shelah, Krueger on the club-isomorphism problem for Aronszajn trees, Neeman on the isomorphism problem for dense sets of reals, and the PI on the Souslin problem. Each of these results was obtained through the development of a completely new technical framework, and these frameworks could now pave the way for the solution of some major open questions. A goal of the highest risk in this project is the discovery of a consistent (possibly, parameterized) forcing axiom that will (preferably, simultaneously) provide structure theorems for stationary sets, linearly ordered sets, trees, graphs, and partition relations, as well as the refutation of various forms of club-guessing principles, all at the level of the second uncountable cardinal. In comparison, at the level of the first uncountable cardinal, a forcing axiom due to Foreman, Magidor and Shelah achieves exactly that. To approach our goals, the proposed project is divided into four core areas: Uncountable trees, Ramsey theory on ordinals, Club-guessing principles, and Forcing Axioms. There is a rich bilateral interaction between any pair of the four different cores, but the proposed division will allow an efficient allocation of manpower, and will increase the chances of parallel success.

1 362 500 €

Start date: 2018-10-01, End date: 2023-09-30

"Combinatorics, and its interplay with geometry, has fascinated our ancestors as shown by early stone carvings in the Neolithic period. Modern combinatorics is motivated by the ubiquity of its structures in both pure and applied mathematics. The work of Hochster and Stanley, who realized the relation of enumerative questions to commutative algebra and toric geometry made a vital contribution to the development of this subject. Their work was a central contribution to the classification of face numbers of simple polytopes, and the initial success lead to a wealth of research in which combinatorial problems were translated to algebra and geometry and then solved using deep results such as Saito's hard Lefschetz theorem. As a caveat, this also made branches of combinatorics reliant on algebra and geometry to provide new ideas. In this proposal, I want to reverse this approach and extend our understanding of geometry and algebra guided by combinatorial methods. In this spirit I propose new combinatorial approaches to the interplay of curvature and topology, to isoperimetry, geometric analysis, and intersection theory, to name a few. In addition, while these subjects are interesting by themselves, they are also designed to advance classical topics, for example, the diameter of polyhedra (as in the Hirsch conjecture), arrangement theory (and the study of arrangement complements), Hodge theory (as in Grothendieck's standard conjectures), and realization problems of discrete objects (as in Connes embedding problem for type II factors). This proposal is supported by the review of some already developed tools, such as relative Stanley--Reisner theory (which is equipped to deal with combinatorial isoperimetries), combinatorial Hodge theory (which extends the ``K\""ahler package'' to purely combinatorial settings), and discrete PDEs (which were used to construct counterexamples to old problems in discrete geometry)."

1 337 200 €

Start date: 2016-12-01, End date: 2021-11-30

"In recent years, the importance of superimposing the contribution of the measure to that of the metric, in determining the underlying space's (generalized Ricci) curvature, has been clarified in the works of Lott, Sturm, Villani and others, following the definition of Curvature-Dimension introduced by Bakry and Emery. We wish to systematically incorporate this important idea of considering the measure and metric in tandem, in the study of questions pertaining to isoperimetric and concentration properties of convex domains in high-dimensional Euclidean space, where a-priori there is only a trivial metric (Euclidean) and trivial measure (Lebesgue). The first step of enriching the class of uniform measures on convex domains to that of non-negatively curved (""log-concave"") measures in Euclidean space has been very successfully implemented in the last decades, leading to substantial progress in our understanding of volumetric properties of convex domains, mostly regarding concentration of linear functionals. However, the potential advantages of altering the Euclidean metric into a more general Riemannian one or exploiting related Riemannian structures have not been systematically explored. Our main paradigm is that in order to progress in non-linear questions pertaining to concentration in Euclidean space, it is imperative to cast and study these problems in the more general Riemannian context. As witnessed by our own work over the last years, we expect that broadening the scope and incorporating tools from the Riemannian world will lead to significant progress in our understanding of the qualitative and quantitative structure of isoperimetric minimizers in the purely Euclidean setting. Such progress would have dramatic impact on long-standing fundamental conjectures regarding concentration of measure on high-dimensional convex domains, as well as other closely related fields such as Probability Theory, Learning Theory, Random Matrix Theory and Algorithmic Geometry."

1 194 190 €

Start date: 2015-10-01, End date: 2020-09-30