Cambridge University

We will consider the following deceptively simple question, formulated recently by Po Shen Loh who connected it to an open problem in Ramsey Theory. Define the '2-less than' relation on the set of triples of integers by saying that a triple x is 2-less than a triple y if x is less than y in at least two coordinates. What is the maximal length of a sequence of triples taking values in {1,...,n} which is totally ordered by the '2-less than' relation?

In his paper, Loh uses the triangle removal lemma to improve slightly on the trivial upper bound of n^2, and conjectures that the truth should be of order n^(3/2). The gap between these bounds has proved to be surprisingly resistant. We shall discuss joint work with Tim Gowers, giving some developments towards this conjecture and a wide array of natural extensions of the problem. Many of these extensions remain open.
 

Let G be a split reductive group over a finite extension k of Q_p. Reeder and Yu have given a new construction of supercuspidal representations of G(k) using geometric invariant theory. Their construction is uniform for all p but requires as input stable vectors in certain representations coming from Moy-Prasad filtrations. In joint work, Jessica Fintzen and I have classified the representations of this kind which contain stable vectors; as a corollary, the construction of Reeder-Yu gives new representations when p is small. In my talk, I will give an overview of this work, as well as explicit examples for the case when G = G_2. For these examples, I will explicitly describe the locus of all stable vectors, as well as the Langlands parameters which correspond under the local Langlands correspondence to the representations of G(k). 

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.