Cambridge University

The class of log-concave densities on $\mathbb{R}^d$ is a very natural infinite-dimensional generalisation of the class of Gaussian densities.  I will show that it also allows the statistician to have the best of both the parametric and nonparametric worlds, in that one can obtain a fully automatic density estimator in the class (via maximum likelihood), with no tuning parameters to choose.  I'll discuss its computation, methodological consequences and theoretical properties, and in particular very recent results on minimax rates of convergence and adaptation.

Given a bipartite graph with m edges, how large is the set of sizes of its induced subgraphs? This question is a natural graph-theoretic generalisation of the 'multiplication table problem' of Erdős:  Erdős’s problem of estimating the number of distinct products a.b with a, b in [n] is precisely the problem under consideration when the graph in question is the complete bipartite graph K_{n,n}.

Based on joint work with J. Sahasrabudhe and I. Tomon.

We consider the problem of large-scale regression where both the number of predictors, p, and the number of observations, n, may be in the order of millions or more. Computing a simple OLS or ridge regression estimator for such data, though potentially sensible from a purely statistical perspective (if n is large enough), can be a real computational challenge. One recent approach to tackling this problem in the common situation where the matrix of predictors is sparse, is to first compress the data by mapping it to an n by L matrix with L << p, using a scheme called b-bit min-wise hashing (Li and König, 2011). We study this technique from a theoretical perspective and obtain finite-sample bounds on the prediction error of regression following such data compression, showing how it exploits the sparsity of the data matrix to achieve good statistical performance. Surprisingly, we also find that a main effects model in the compressed data is able to approximate an interaction model in the original data. Fitting interactions requires no modification of the compression scheme, but only a higher-dimensional mapping with a larger L.
This is joint work with Nicolai Meinshausen (ETH Zürich).

Erdős asked the following question: given a positive integer $n$, what is the largest integer $k$ such that any set of $n$ points in a plane, with no $4$ on a line, contains $k$ points no $3$ of which are collinear? Füredi proved that $k = o(n)$. Cardinal, Toth and Wood extended this result to $\mathbb{R}^3$, finding sets of $n$ points with no $5$ on a plane whose subsets with no $4$ points on a plane have size $o(n)$, and asked the question for the higher dimensions. For given $n$, let $k$ be largest integer such that any set of $n$ points in $\mathbb{R}^d$ with no more than $d + 1$ cohyperplanar points, has $k$ points with no $d + 1$ on a hyperplane. Is $k = o(n)$? We prove that $k = o(n)$ for any fixed $d \geq 3$.

The Number Field Sieve is the current practical and theoretical state of the art algorithm for factoring. Unfortunately, there has been no rigorous analysis of this type of algorithm. We randomise key aspects of the number theory, and prove that in this variant congruences of squares are formed in expected time $L(1/3, 2.88)$. These results are tightly coupled to recent progress on the distribution of smooth numbers, and we provide additional tools to turn progress on these problems into improved bounds.

Given two probability distributions $P_R$ and $P_B$ on the positive reals with finite means, colour the real line alternately with red and blue intervals so that the lengths of the red intervals have distribution $P_R$, the lengths of the blue intervals have distribution $P_B$, and distinct intervals have independent lengths. Now iteratively update this colouring of the line by coalescing intervals: change the colour of any interval that is surrounded by longer intervals so that these three consecutive intervals subsequently form a single monochromatic interval. Say that a colour (either red or blue) `wins' if every point of the line is eventually of that colour. I will attempt to answer the following question: under what natural conditions on the distributions is one of the colours almost surely guaranteed to win?

We shall discuss the problem of the 'trend to equilibrium' for a 

degenerate kinetic linear Fokker-Planck equation. The linear equation is 

assumed to be degenerate on a subregion of non-zero Lebesgue measure in the 

physical space (i.e., the equation is just a transport equation with a 

Hamiltonian structure in the subregion). We shall give necessary and 

sufficient geometric condition on the region of degeneracy which guarantees 

the exponential decay of the semigroup generated by the degenerate kinetic 

equation towards a global Maxwellian equilibrium in a weighted Hilbert 

space. The approach is strongly influenced by C. Villani's strategy of 

'Hypocoercivity' from Kinetic theory and the 'Bardos-Lebeau-Rauch' 

geometric condition from Control theory. This is a joint work with Frederic 

Herau and Clement Mouhot.