• The Interplay between High-Dimensional Geometry and Probability
• Problem Groups

• Description
• Winter School on The Interplay between High-Dimensional Geometry and Probability (January 11-15, 2021)
• Workshop: High dimensional spatial random systems (February 22-26, 2021)
• Workshop: High dimensional measures: geometric and probabilistic aspects (March 22-26, 2021)
• Trimester Seminar Series
• Prerecorded Videos
• Problem Groups
• Participants
• Poster
• Final Report
• Getting to HIM

Problem Groups

Every participant of the trimester program is welcome to open a problem group working on specific topics or to join one of the existing problem groups. Please fill out the online form below if you are interested in such activities. If a certain group of participants has already agreed to work on a topic, please make clear in the form whether this group is "closed" or still "open" for further members. Each group will be provided with the necessary infrastructure to work together online and in a seminar room, for those who are in Bonn.

Problem Group 1: Random polytopes in spherical geometries (closed)

We are studying the expected f-vector of spherical random convex hulls generated by $n$ random points uniformly distributed in a spherically convex set. Our focus is on the asymptotic behavior as $n\to\infty$. In particular, we are aiming at an interpolation of the result for the half-sphere (where the expected f-vector converges in law and in $L^1$ to a constant random vector without any renormalization) and the case of a proper spherically convex set (in which case the one has $L^1$-convergence after a proper renormalization).

Group members:
Florian Besau
Anna Gusakova
Matthias Reitzner
Carsten Schütt
Christoph Thäle (contact: christoph.thaele(at)rub.de)
Elisabeth Werner

Problem Group 2: Towards the Aaronson-Ambainis conjecture (open)

The Aaronson-Ambianis conjecture (Conjecture 6 here: https://arxiv.org/pdf/0911.0996.pdf) asserts that if $f:\{-1,1\}^n \to [-1,1]$ is of degree d with $\mathrm{Var}[f] = \Omega(1)$ then f has at least one influence of order $1/poly(d)$. This question can be rephrased in terms of a bound on the diameter of a certain convex set which is the intersection of linear and quadratic constraints: Consider the Fourier coefficients of the function $f$ which can be thought of as a function $g:2^{[n]} \to \mathbb{R}$. Consider the polytope representing Fourier coefficients of bounded functions, namely for all $x \in \{-1,1\}^n$ one obtains a constraint $\sum_{A \subset [n]} g(A) \xi_A(x)$ where $\xi_A(x) := \prod_{i \in A} x_i$. Intersect this polytope with the "small influence" constraints $\sum_{i \in A \subset [n]} g(A)^2 \leq d^{-100}$ for all $i \in [n]$, to obtain a convex set $K$. The A-A conjecture essentially asserts that the diameter of $K$ goes to zero. The goal of this problem group is to look into polytopes obtained from the Fourier coefficients of functions on the Boolean hypercube and see whether we can find some interplay between convexity and Boolean functions, hopefully towards progress on celebrated conjecture.

Group members:
Radoslaw Adamczak
Ronen Eldan (contact: roneneldan(at)gmail.com)
Alexandros Eskenazis
Uri Grupel
Yihan Zhang

Problem Group 3: Polynomial Hirsch Conjecture for Random Polytopes (open)

The combinatorial diameter of polytope $P = \{x \in R^n: Ax \leq b\}$, $A \in R^{m \times n}$, $b \in R^m$, is the diameter of 1-skeleton $G_P$ of $P$, which is the graph formed by edges and vertices of $P$. More precisely, it is the maximum shortest path distance between any two vertices in $G_P$, measured by the number of edges in the path. A long-standing conjecture is the so-called polynomial Hirsch conjecture, which posits that the diameter of $G_P$ is always bounded by a polynomial ${poly}(n,m)$, in the dimension and the number of facets. The best current estimates are quasi-polynomial $2^{O(\log n \log m)}$, due to Kalai and Kleitman (see https://pubsonline.informs.org/doi/10.1287/moor.1100.0470 for a very nice presentation of known bounds).

To make progress on this conjecture, we propose to study the polynomial Hirsch conjecture for random polytopes. A prototypical question is as follows: given a random polytope $P := \{Ax \leq 1\}$, $A \in R^{m \times n}$, where the entries of $A$ are i.i.d. $N(0,1)$, prove that the combinatorial diameter of $G_P$ is polynomial in $m$ and $n$ with high probability. For this project, we will first explore whether variants of shadow vertex simplex algorithm, allow us to get useful bounds for this problem (see https://arxiv.org/abs/1412.6705 for details).

Group members:
Daniel Dadush (contact: dndadush(at)gmail.com)
Uri Grupel
Orli Herscovici
Sophie Huiberts
Ben Li
Galyna Livshyts
Carsten Schuett
Elisabeth Werner

Problem Group 4: Convex Geometry in Depth (closed)

With each integrable multivariate distribution, it is possible to associate a family of convex bodies called zonoid trimmed regions.

If a random vector is uniformly distributed on a convex body, this map transforms a convex body and provides a variant of a well known convex floating body concept. A particular feature of this map is its sublinearity with respect to the Minkowski addition.

The aim of this group is to study properties of such nonlinear maps between convex bodies, in particular, their identification and uniqueness. The effects arising from increasing dimension will be also explored. Such maps are important in statistics, where they define depth functions useful to identify outliers. In finance, such set-valued maps arise from risk assessment of multivariate portfolios, however, then one works with superadditive set-valued maps, which cannot be converted to sublinear ones by a simple change of sign.

Group members:
Petra Laketa
Ilya Molchanov (contact: ilya.molchanov(at)stat.unibe.ch)
Stanislav Nagy
Carsten Schütt
Elisabeth Werner