Institute for Computational and Experimental Research in Mathematics (ICERM)

Abstract

We discuss upper bounds for the Fisher information in high dimensions in terms of the total variation and norms in Sobolev spaces.

• Video

Abstract

Finding a simple description of a convex hull of a set K in n-dimensional Euclidean space is a basic problem in mathematics. When K has some additional geometric structures one may hope to give an explicit construction of its convex hull. A good starting point is when K is a space curve. In this talk I will describe convex hulls of space curves which have a "very" positive torsion. In particular, we obtain a parametric representation of the boundary of the convex hull, different formulas for their Euclidean volumes and the surface areas, and the solution to a general moment problem corresponding to such curves. This is joint work with Jaume de Dios Pont and Jose Ramon Madrid Padilla.

• Video

Abstract

I will discuss several conjectures about level sets of eigenfunctions in convex domains.

Abstract

While there is extensive literature on approximation, deterministic as well as random, of general convex bodies in the symmetric difference metric, or other metrics coming from intrinsic volumes, very little is known for corresponding random results in the Hausdorff distance. For a polygon Q in the plane, the convex hull of n points chosen at random on the boundary of Q gives a random polygon Q_n. We determine the exact limiting behavior of the expected Hausdorff distance between Q and a random polygon Q_n as the number n of points chosen on the boundary of Q goes to infinity. Based on joint work with J. Prochno, C. Schuett and M. Sonnleitner.

• Video

Abstract

Generalized Probabilistic Theories (GPTs) are theories of nature that have random features. A GPT must specify the set of states purporting to represent the physical reality, the allowable measurements, the rules for outcome statistics of the latter, and the composition rules describing what happens when we merge subsystems and create a larger system. Examples include classical probability and quantum theory. The composition rules alluded to above usually involve tensor products, including tensor products of normed spaces, convex sets and of cones. Among tensor products that have operational meaning in the GPT context, the projective and the injective product are the extreme ones, which leads to the natural question "How much do they differ?" considered already by Grothendieck and Pisier (in the 1950s and 1980s). We report on quantitative results concerning projective/injective discrepancy for finite-dimensional normed spaces. Some of the results are essentially optimal, but others can be likely improved. The methods involve a wide range of techniques from geometry of Banach spaces and random matrices. We also report on parallel results in the context of cones. Finally, we will encourage a more systematic study of convex bodies with the allowed morphisms being projective transformations. Joint work with G. Aubrun, L. Lami, C. Palazuelos, A. Winter (and a parallel work by a subset of co-authors and M. Plavala).

• Video
• Slides

Abstract

I will provide a survey of large deviation principles for projections of high-dimensional convex bodies. This is based on various joint works with N. Gantert, S.S. Kim, Y.-T. Liao, P. Lopatto and D. Xie.

Abstract

Many of us use smartphones and rely on tools like auto-complete and spelling auto-correct to make using these devices more pleasant, but building these tools presents a challenge. On the one hand, the machine-learning algorithms used to provide these features require data to learn from, but on the other hand, who among us is willing to send a carbon copy of all our text messages to device manufacturers to provide that data? "Local differential privacy" (LDP) and related models have become the gold standard for understanding the tradeoffs possible between utility and privacy loss. In this talk we present a new LDP mechanism for estimating data histograms over large numbers of users, making use of projective geometry together with a dynamic programming based reconstruction algorithm. I will also mention the opportunity for tools from this community to have impact in mobile devices, e.g. the SQKR mechanism of [Chen, Kairouz, Ozgur'20] on private mean estimation using work on Kashin representations by Lyubarskii and Vershynin. This talk is based on joint work with Vitaly Feldman (Apple), Huy Le Nguyen (Northeastern), and Kunal Talwar (Apple).

• Video

Abstract

Using aspects of Talagrand's generic chaining theory, we show how to construct spectral hypergraph eps-sparsifiers with only O(eps^{-2} log(r) n log n) hyperedges, where n is the number of vertices and r is the rank of the hypergraph.

Abstract

A well known conjecture of Burr and Erdos asserts that the Ramsey number of the hypercube on 2^n vertices is of the order O(2^n). Motivated by this problem, we construct randomized embeddings of the hypercube into dense bipartite graphs and, as a corollary, show that the Ramsey number of the hypercube is of order O(2^{2n−cn}) for a universal constant c>0. This improves upon the previous best known bound O(2^{2n}), due to Conlon, Fox and Sudakov.

Abstract

We shall discuss results and open questions pertaining to the regularity (and irregularity) of solutions of weighted isoperimetric-type problems over the class of symmetric convex sets. Based on joint work with G. Moschidis (EPFL)

Abstract

The Gaussian Elimination with Partial Pivoting (GEPP) is a classical algorithm for solving systems of linear equations. Although in specific cases the loss of precision in GEPP due to roundoff errors can be very significant, empirical evidence strongly suggests that for a typical square coefficient matrix, GEPP is numerically stable. We obtain a (partial) theoretical justification of this phenomenon by showing that, given the random n x n standard Gaussian coefficient matrix A, the growth factor of the Gaussian Elimination with Partial Pivoting is at most polynomially large in n with probability close to one. This implies that with high probability the number of bits of precision sufficient to solve Ax=b to m bits of accuracy using GEPP is m + O(log(n)), which improves an earlier estimate m + O( log^2 n) of Sankar, and which we conjecture to be optimal by the order of magnitude. We further provide tail estimates of the growth factor which can be used to support the empirical observation that GEPP is more stable than the Gaussian Elimination with no pivoting. This talk is based on a joint work with Konstantin Tikhomirov.

• Video

Abstract

Let $X=(\xi_1, ..., \xi_m)$ be a centered Gaussian random vector, such that the variances of each $\xi_i$ equals to 1. Under what assumptions on the covariance matrix is the expectation of $\min_i |\xi_i|$ minimized? We discuss known results and conjectures related to this question.

• Video

Abstract

We will consider several classical problems for hypoelliptic diffusions and random walks: the large deviations principle (LDP), the small ball problem (SBP), Chung’s law of iterated logarithm (LIL), and finding the Onsager-Machlup functional. As two very different examples we will look at hypoelliptic Brownian motion and the corresponding random walk on the Heisenberg group, and the Kolmogorov diffusion. We will explore the role of space-time scaling property, Gaussianity, and spectral properties via Dirichlet forms in these settings. The Onsager-Machlup functional is used to describe the dynamics of a continuous stochastic process, and it is closely related to the SBP and LIL, as well as the rate functional in the LDP. Unlike in the elliptic (Riemannian) case we do not rely on the tools from differential geometry such as comparison theorems or curvature bounds as these are not always available in the hypoelliptic (sub-Riemannian) setting. The talk is based on the joint work with Marco Carfagnini, Tai Melcher and Jing Wang.

• Video

Abstract

Random polynomials have been studied since the early 1900s with notable publications by Erdos, Kac, Littlewood, Offord, and others. In recent years, universality has emerged as a powerful method that systematically tackles long-standing problems on the distribution of roots. In this talk, I will discuss a general framework to establish universality properties. I shall go over the application of this framework to different families of polynomials and how to use these properties to answer classical questions in the field. This is based on joint work with Yen Do, Doron Lubinsky, Hoi Nguyen, Igor Pritsker, and Van Vu.

Abstract

A basic problem in probability theory and engineering is finding a way of representing a complicated probability measure as a simpler probability measure under some transformation. A desirable property of such transformations is that it is Lipschitz, since it allows for information from the simpler probability measure to be transferred to the complicated measure. While various transformations (optimal transport, Knothe-Rosenblatt rearrangement) exist, establishing their regularity is a difficult problem. In this talk, I will discuss the Lipschitz properties of the Langevin transport map which is constructed infinitesimally along the Langevin dynamics. I will show that this map is Lipschitz in many settings where no other Lipschitz transport maps are known to exist. I will conclude the talk by introducing a new connection between the Langevin transport map and renormalization groups methods from quantum and statistical field theories.

Abstract

The Brunn-Minkowski inequality fails dramatically on the hyperbolic plane. We show that this can be remedied by defining Minkowski summation with horocycles instead of geodesics. Joint with Bo'az Klartag.

• Video

Abstract

We will show that for any even log-concave measure \mu and any pair of symmetric convex sets K and L, and any t between 0 and 1, one has the inequality: \mu(tK+(1-t)L)^{c(n)}\geq t\mu(K)^{c(n)}+(1-t)\mu(L)^{c(n)}, Where c(n)=n^{-4-o(1)}. This constitutes progress towards the Dimensional Brunn-Minkowski conjecture.

• Video

Abstract

We discuss the method of bounding suprema of canonical processes based on the inclusion of their index set into a convex hull of a well-controlled set of points. While the upper bound is immediate, the reverse estimate was established to date only for a narrow class of regular stochastic processes (for which the chaining method works). We show that for specific index sets, including arbitrary ellipsoids, regularity assumptions may be substantially weakened.

• Video
• Slides

Abstract

A positive correlation inequality is established for circular-invariant plurisubharmonic functions, with respect to complex Gaussian measures. The main ingredients of the proofs are the Ornstein-Uhlenbeck semigroup, and another natural semigroup associated to the Gaussian dbar-Laplacian. Joint work with Franck Barthe.

Abstract

Let P be a bounded polyhedron, defined as the intersection of the non-negative orthant in R^n and an affine subspace of codimension m. I present a simple and computationally efficient formula that approximates the volume of P within a factor c^m, where c > 0 is an absolute constant. This is joint work with Mark Rudelson.

• Video

Abstract

We prove that Bourgain’s hyperplane conjecture and the Kannan-Lovasz-Simonovits isoperimetric conjecture hold true up to a factor that is polylogarithmic in the dimension.

• Video

Abstract

We refine the recent breakthrough technique of Klartag and Lehec to obtain an improved polylogarithmic bound for the KLS constant.

• Video

Abstract

We revisit the notion of noise stability in the hypercube and show how one can replace the usual heat semigroup with more general stochastic processes. We will then introduce a re-normalized Brownian motion, embedding the discrete hypercube into the Wiener space, and analyze the noise stability along its paths. Our approach leads to a new quantitative form of the 'Majority is Stablest' theorem from Boolean analysis and to progress on the 'most informative bit' conjecture of Courtade and Kumar.

• Video