CS Theory -- Erdős Lecture II: Counting contigency tables

Date: 
Wed, 12/12/201810:30-12:00
Location: 
Rothberg (CS building) B-220
Lecturer: 
Igor Pak (UCLA)

Contingency tables are matrices with fixed row and column sums.  They are in natural correspondence with bipartite multi-graphs with fixed degrees and can also be viewed as integer points in transportation polytopes.  Counting and random sampling of contingency tables is a fundamental problem in statistics which remains unresolved in full generality.  

In the talk, I will review both asymptotic and MCMC approaches, and then present a new Markov chain construction which provably works for sparse margins.  I conclude with some curious experimental results and conjectures. 

Joint work with Sam Dittmer. 

This talk is independent of the first Erdős Lecture.