Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Extremal set theory II

Andrey Kupavskii
Member, School of Mathematics
November 5, 2019

Extremal set theory typically asks for the largest collection of sets satisfying certain constraints. In the first talk of these series, I'll cover some of the classical results and methods in extremal set theory. In particular, I'll cover the recent progress in the Erdos Matching Conjecture, which suggests the largest size of a family of k-subsets of an n-element set with no s pairwise disjoint sets.

Privacy via ill-posedness

Anna Gilbert
University of Michigan; Member, School of Mathematics
November 4, 2019

In this work, we exploit the ill-posedness of linear inverse
problems to design algoithms to release differentially private data or
measurements of the physical system. We discuss the spectral
requirements on a matrix such that only a small amount of noise is
needed to achieve privacy and contrast this with the poor conditioning
of the system. We then instantiate our framework with several
diffusion operators and explore recovery via l1 constrained
minimisation. Our work indicates that it is possible to produce

Extremal set theory I

Andrey Kupavskii
Member, School of Mathematics
October 29, 2019

Extremal set theory typically asks for the largest collection of sets satisfying certain constraints. In the first talk of these series, I'll cover some of the classical results and methods in extremal set theory. In particular, I'll cover the recent progress in the Erdos Matching Conjecture, which suggests the largest size of a family of k-subsets of an n-element set with no s pairwise disjoint sets.

Asymptotic spectra and Applications II

Jeroen Zuiddam
Member, School of Mathematics
October 15, 2019

In this second lecture in my series on asymptotic spectra we will focus on one application: the matrix multiplication problem. We will use the asymptotic spectrum of tensors to prove that a very general method (that includes the methods used to obtain the currently best algorithms) cannot give faster matrix multiplication algorithms. Keywords are Shannon entropy, representation theory and moment polytopes, but prior knowledge of these is not assumed.

Asymptotic spectra and Applications I

Jeroen Zuiddam
Member, School of Mathematics
October 8, 2019

The first lecture in this series is an introduction to the theory of asymptotic spectra. This theory describes asymptotic behavior of basic objects in mathematics like graphs and tensors. Example applications that we will see are the matrix multiplication problem, the cap set problem, the sunflower problem, the quantum entanglement problem, and the problem of efficient communication over a noisy channel. We will start from scratch.