We establish and generalise several bounds for various random walk quantities including the mixing time and the maximum hitting time. Unlike previous analyses, our derivations are based on rather intuitive notions of local expansion properties which allows us to capture the progress the random walk makes through t-step probabilities. We apply our framework to dynamically changing graphs, where the set of vertices is fixed while the set of edges changes in each round.

For random walks on dynamic connected graphs for which the stationary distribution does not change over time, we show that their behaviour is in a certain sense similar to static graphs. For example, we show that the mixing and hitting times of any sequence of d-regular connected graphs is O(n²), generalising a well-known result for static graphs. Finally, we investigate properties of random walks on dynamic graphs that are not always connected: we relate their convergence to stationarity to the spectral properties of an average of transition matrices and provide some examples that demonstrate strong discrepancies between static and dynamic graphs.

In recent years, the LOCAL model has seen the emergence of a new technique, called "round elimination", that lies at the core of new lower bounds for important problems such as the Lovász Local Lemma, Maximal Matching, or Maximal Independent Set. Despite its conceptual simplicity, it has become one of the main tools in proving round complexity lower bounds for locally checkable problems.

The fundamental insight behind this technique is that, roughly speaking, for each locally checkable problem P, there is another problem P₁ that can be solved exactly one round faster. By applying this insight iteratively, obtaining problems P₁, P₂, … with decreasing complexities, the complexity of P can be bounded by checking which of the P_i is the first problem in the sequence that can be solved in 0 rounds. As we will see, the above sequence of problems can be obtained in a fully automated way, opening new and exciting possibilities for obtaining improved complexity bounds for locally checkable problems. In this talk, we will take an in-depth look at the round elimination technique, its inner workings, potential and limitations.

We are trying to answer questions such as whether random graphs have the least structure among all locally equivalent graphs. More precisely, we focus on locally defined optimization problems on bounded-degree graphs such as finding a large matching or independent set. In random graphs, our best algorithms for these problems can be approximated by constant-time randomized distributed algorithms called local algorithms. We give an overview about positive and negative results about what can be constructed by them, including some very recent algorithms and entropic bounds. All these questions have strong connections to sparse graph limit theory and statistical physics.

As a fundamental tool in modeling and analyzing real world data, large-scale algorithms are a central part of any tool set for big data analysis. Processing datasets with hundreds of billions of entries is only possible via developing distributed algorithms under distributed frameworks such as MapReduce, Pregel, Gigraph, and alike. For these distributed algorithms to work well in practice, we need to take into account several metrics such as the number of rounds of computation and the communication complexity of each round. In this talk, we discuss the design and implementation of algorithms based on traditional MapReduce architecture. In this regard, we focus on the MPC model and we consider different clustering problems.

Expander decomposition has been a central tool in designing graph algorithms in many fields (including fast centralized algorithms, approximation algorithms and property testing) for decades. Recently, we found that it also gives many impressive applications in dynamic graph algorithms and distributed graph algorithms. In this talk, I will survey these recent results based on expander decomposition, explain the key components for using this technique, and give some toy examples on how to apply these components.

In this talk we will survey some of the recent work on distributed property testing in the networks with bounded bandwidth (the CONGEST model). Property testing is a relaxation of the standard notion of a decision problem, where instead of deciding if the input satisfies some property or not, we are only interested in distinguishing the case where the input has the property from the case where it is far from having the property, in the sense that many bits in the representation of the input would need to be changed to make it satisfy the property. In the case of graph problems, this means adding or removing many edges to the graph. Classical problems studied in the sequential setting include testing subgraph-freeness, bipartiteness, planarity, and many other problems. Several of these have now been studied in the CONGEST model, and I will talk about some of the results, some open problems, and why we currently have very few lower bounds.