Day 1: June 09th, 2016.
Afternoon Session
14h00-14h45: Kevin Perrot, Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape (part 1)
14h45-15h00: Coffee break
15h00-15h45: Nguyen Huy Truong, Introduction to Markov chain mixing
15h45-16h00: Coffee break
16h00-16h45: Nguyen Hoang Thach, Rotor Walks and Markov Chains
=====================
Day 2: June 10th, 2016.
Morning Session
09h00-09h45: Phan Thi Ha Duong, Linear time algorithm for computing the rank of divisors on cactus graphs (part 1)
09h45-10h00: Coffee break
10h00-10h45: Phan Thi Ha Duong, Linear time algorithm for computing the rank of divisors on cactus graphs (part 2)
10h45-11h00: Coffee break
11h00-11h45: Chloe Hebrand, On the efficiency of some algorithms on cryptography
11h45-14h00: Lunch break
Afternoon Session
14h00-14h45: Kevin Perrot, Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape (part 2)
14h45-15h00: Coffee break
15h00-15h45: Le Chi Ngoc, Markov chain Monte Carlo: Metropolis and Glauber chains
15h45-16h00: Coffee break
16h00-16h45: Nguyen Hoang Thach, Coupling of Markov chains
=====================
Day 3: June 11th, 2016.
Morning Session
09h00-09h45: Ta Duy Hoang, Strong stationary times (part 1)
09h45-10h00: Coffee break
10h00-10h45: Ta Duy Hoang, Strong stationary times (part 2)
10h45-11h00: Coffee break
11h00-11h45: Le Chi Ngoc, Lower bounds on mixing times
11h45-14h00: Lunch
=====================
ABSTRACT
Kadanoff Sand Pile Model. Avalanche Structure and Wave Shape. (2 parts)
Speaker: Kevin Perrot (Université Aix Marseille)
Abstract:
Sand pile models are dynamical systems describing the evolution from N stacked grains to a stable configuration. It uses local rules to depict grain moves and iterate it until reaching a fixed configuration from which no rule can be applied. Physicists L. Kadanoff et al inspire KSPM, extending the well known Sand Pile Model (SPM). I KSPM(D), we start from a pile of N stacked grains and apply the rule: D−1 grains can fall from column i onto columns i+1, i+2, . . . , i+D−1 if the difference of height between columns i and i+1 is greater or equal to D. Toward the study of fixed points (stable configurations on which no grain can move) obtained from N stacked grains, we propose an iterative study of KSPM evolution consisting in the repeated addition of one grain on
a heap of sand, triggering an avalanche at each iteration. We develop a formal background for the study of avalanches, resumed in a finite state word transducer, and explain how this transducer may be used to predict the form of fixed points. Further precise developments provide a plain formula for fixed points of KSPM(3), showing the emergence of a wavy shape.
Linear time algorithm for computing the rank of divisors on cactus graphs
Speaker: Phan Thi Ha Duong (Institute of mathematics, VAST)
Abstract: Rank of divisor on graph was introduced in 2007 and it quickly attracts many attentions. Recently in 2015, the problem of computing this quantity was proved to be NP-hard. In this paper, we describe a linear time algorithm for this problem limited on cactus graphs.
Rotor Walks and Markov Chains
Speaker: Nguyen Hoang Thach (Institute of mathematics, VAST)
Abstract: The rotor walk is a derandomized version of the random walk on a graph. On successive visits to any given vertex, the walker is routed to each of the neighboring vertices in some fixed cyclic order, rather than to a random sequence of neighbors. The concept generalizes naturally to countable Markov chains. Subject to general conditions, we prove that many natural quantities associated with the rotor walk (including normalized hitting frequencies, hitting times and occupation frequencies) concentrate around their expected values for the random walk. Furthermore, the concentration is stronger than that associated with repeated runs of the random walk; the discrepancy is at most C/n after n runs (for an explicit constant C), rather than c/ sqrt(n).
Markov chain Monte Carlo: Metropolis and Glauber chains
Speaker: Le Chi Ngoc (Hanoi University of Science and Technology)
Abstract: We present two methods to find Markov chains with a given stationary distribution: the Metropolis chains and the Glauber dynamics.
Introduction to Markov chain mixing
Speaker: Nguyen Huy Truong (Hanoi University of Science and Technology)
Abstract: We define the total variation distance and give several useful characterizations of it. Next, we prove that for irreducible and aperiodic chains, the distribution after many steps converges to the stationary distribution, in the sense that the TV distance between them converges to 0. Then we define the mixing times of a chain. Finally, we prove a version of the Ergodic theorem for Markov chains.
Coupling of Markov chains
Speaker: Nguyen Hoang Thach (Institute of mathematics, VAST)
Abstract: We introduce coupling as a technique to obtain upper bounds of the mixing time of a Markov chain. We use this technique to give upper bounds of mixing time for random walks on various types of graphs: the cycle, the torus, the hypercube, the binary tree. We also give upper bounds of mixing time for the Metropolis chain on the set of proper colorings and the Glauber chain for the hardcore model.
Strong stationary times (2 parts)
Speaker: Ta Duy Hoang (Hanoi University of Science and Technology)
Abstract: We introduce the notions of stopping time, strong stationary time, separation distance and how to use them to obtain upper bounds on mixing time of Markov chains.
Lower bounds on mixing times
Speaker: Le Chi Ngoc (Hanoi University of Science and Technology)
Abstract: We discuss several methods to obtain lower bounds on mixing times of Markov chains.
On the efficiency of some algorithms on cryptography
Speaker: Chloe Hebrand (Université de Limoges)
Abstract: Algorithmic simplicity, efficiency, and parallelism. Lattice-based cryptosystems are often algorithmically simple and highly parallelizable, consisting mainly of linear operations on vectors and matrices modulo relatively small integers. Moreover, constructions based on “algebraic” lattices over certain rings (e.g., the NTRU cryptosystem [HPS98]) can be especially efficient, and in some cases even outperform more traditional systems by a significant margin.