Tue, 03 May 2016
14:30
L6

The Multiplication Table Problem for Bipartite Graphs

Bhargav Narayanan
(Cambridge University)
Abstract

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.

Mon, 27 Apr 2015
14:15

Min-wise hashing for large-scale regression

Rajen Shah
(Cambridge University)
Abstract

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).

Tue, 17 Feb 2015
14:30
L6

Monochromatic cycle partitions - an exact result

Shoham Letzter
(Cambridge University)
Abstract
In 2011, Schelp introduced the idea of considering Ramsey-Turán type problems for graphs with large minimum degree. Inspired by his questions, Balogh, Barat, Gerbner, Gyárfás, and Sárközy suggested the following conjecture. Let $G$ be a graph on $n$ vertices with minimum degree at least $3n/4$. Then for every red and blue colouring of the edges of $G$, the vertices of $G$ may be partitioned into two vertex-disjoint cycles, one red and the other blue. They proved an approximate version of the conjecture, and recently DeBiasio and Nelsen obtained stronger approximate results. We prove the conjecture exactly (for large $n$). I will give an overview of the history of this problem and describe some of the tools that are used for the proof. I will finish with a discussion of possible future work for which the methods we use may be applicable.
Tue, 10 Feb 2015
14:30
L6

Points in almost general position

Luka Milicevic
(Cambridge University)
Abstract

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$.

Tue, 03 Feb 2015
14:30
L6

Rigorous analysis of a randomised number field sieve

Jonathan Lee
(Cambridge University)
Abstract

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.

Tue, 27 Jan 2015
14:30
L6

Coalescence on the real line

Bhargav Narayanan
(Cambridge University)
Abstract

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?

Thu, 22 Jan 2015

12:00 - 13:00
L6

HYPOCOERCIVITY AND GEOMETRIC CONDITIONS IN KINETIC THEORY.

Harsha Hutridurga
(Cambridge University)
Abstract
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.
Fri, 28 Feb 2014

16:00 - 17:00
L4

CALF: A period map for global derived stacks

Carmelo Di Natale
(Cambridge University)
Abstract

In the sixties Griffiths constructed a holomorphic map, known as the local period map, which relates the classification of smooth projective varieties to the associated Hodge structures. Fiorenza and Manetti have recently described it in terms of Schlessinger's deformation functors and, together with Martinengo, have started to look at it in the context of Derived Deformation Theory. In this talk we propose a rigorous way to lift such an extended version of Griffiths period map to a morphism of derived deformation functors and use this to construct a period morphism for global derived stacks.

Subscribe to Cambridge University