Abstract: Despite hostility from the theoretical CS community, sequential importance sampling remains a widely used (and useful) family of algorithms. In joint work with Yeganeh Alimohammadi, Mohamad Roghani, and Amin Saberi, we prove polynomial time guarantees for bipartite matching for dense graphs. It's utility is illustrated for three real world counting and generation problems: Generating Latin squares, card guessing experiments with feedback and stochastic block models. Our implementations illustrate the strengths and weaknesses of Sinkhorn scaling for evaluating the permanent.

Bio: Persi Diaconis is Professor of Mathematics and Statistics at Stanford University. He works in probability, combinatorics, mathematical statistics and group theory. Perhaps most well known for proving that 'Seven ordinary riffle shuffles are necessary and suffice to mix up 52 cards'. This is a typical result in a main interest; proving rates of convergence to equilibrium for widely used Markov Chain Monte Carlo algorithms. In combinatorics he works on the enumerative, probabilistic side; pick and x in X at random, what does it look like? This often leans on tools like symmetric function theory. In Mathematical statistics, he proves (and disproves) things about Bayesian procedures; the standard notion of conjugate prior and the inconsistency of Bayes procedures in non-parametric problems. In Group theory he has developed new 'supercharacter theories' for provably intractable cases and the 7/9 theorem; if S is a subset of the finite group G and the chance that the product of a pair of random elements of S is in S is larger than 7/9 then S is a subgroup. For most of his career he has been fascinated by the interface between 'the art of computer programming' and his areas of expertise.