Ofer Ben Mordehi
Probability of a group acting on a locally finite rooted tree T

The group Aut(T) is a compact group hence has a probability Haar measure. This raises a number of questions on random groups generated by a Haar random element b\in Aut(T). I want to answer the following question: If a countable group acts essentially free on the boundary of T then how does the group < G,b> act ?

It is well-known that triangulations of the convex n-gon are in one-to-one correspondence with binary trees with n leaves. The most natural way to construct a random triangulation of the convex n-gon (i.e. step by step) leads to a random tree with typical size of order n^(\sqrt{17}-3)/2. I will try to explain where does this exponent come from.

Klim Efremenko
How Well Do Random Walks Parallelize?

A random walk on a graph is a process that explores the graph in a random way: at each step the walk is at a vertex of the graph, and at each step it moves to a uniformly selected neighbor of this vertex. Random walks are extremely useful in computer science and in other fields. A very natural problem that was recently raised by Alon, Avin, Koucky, Kozma, Lotker, and Tuttle (though it was implicit in several previous papers) is to analyze the behavior of k independent walks in comparison with the behavior of a single walk. In particular, Alon et al. showed that in various settings (e.g., for expander graphs), k random walks cover the graph (i.e., visit all its nodes), Omega(k)-times faster (in expectation) than a single walk. In other words, in such cases k random walks efficiently ``parallelize" a single random walk. Alon et al.\ also demonstrated that, depending on the specific setting, this ``speedup" can vary from logarithmic to exponential in k. In this paper we initiate a more systematic study of multiple random walks. We give lower and upper bounds both on the cover time and on the hitting time (the time it takes to hit one specific node) of multiple random walks. Our study revolves over three alternatives for the starting vertices of the random walks: the worst starting vertices (those who maximize the hitting/cover time), the best starting vertices, and starting vertices selected from the stationary distribution. Among our results, we show that the speedup when starting the walks at the worst vertices cannot be too large - the hitting time cannot improve by more than an O(k)factor and the cover time cannot improve by more than \min\{k \log n,k2\} (where n is the number of vertices). These results should be contrasted with the fact that there was no previously known upper-bound on the speedup and that the speedup can even be exponential in k for random starting vertices. We further show that for k that is not too large (as a function of various parameters of the graph), the speedup in cover time is O(k) even for walks that start from the best vertices (those that minimize the cover time). As a rather surprising corollary of our theorems, we obtain a new bound which relates the cover time C and the mixing time of a graph. Specifically, we show that C=O(m sqrt{mix} log ^2 n) (where m is the number of edges).

Shahar Golan
Minesweeper on graphs

Minesweeper is a popular single player game. It has been shown that the Minesweeper consistency problem is NP-complete and the Minesweeper counting problem is #P-complete. In this paper, we present efficient algorithms for solving these problems for minesweeper graphs with bounded treewidth. Our algorithms turn out to be much better than those based directly on dynamic programming. The algorithms mostly use of algebraic operations on multivariate polynomials, so that one may use existing software to implement them easily.

Ori Hirschberg
Condensation in temporally correlated zero-range dynamics

Condensation phenomena in non-equilibrium systems have been modeled by the zero range process, which is a model of particles hopping between boxes with Markovian dynamics. In many cases, memory effects in the dynamics cannot be neglected. In an attempt to understand the possible impact of temporal correlations on the condensate, a process with non-Markovian zero range dynamics is introduced and studied. Two main results are found: (1) In mean-field dynamics, the steady state corresponds to that of a Markovian ZRP, but with modified hopping rates which can affect condensation, and (2) for nearest-neighbor hopping in one dimension, the condensate occupies two adjacent sites on the lattice and drifts with a finite velocity.

Nathan Keller
A simple reduction from the biased measure on the discrete cube to the uniform measure

Properties of the Fourier expansion of functions on the discrete cube were intensively investigated in the last two decades, and this study led to important applications in numerous fields, including Theoretical Computer Science, Mathematical Physics, Social Choice Theory, etc. Most of the results in the field consider the uniform probability measure on the discrete cube. However, some of the applications require consideration of a biased measure instead of the uniform measure, which led to generalizations of some of the results to the biased measure. Usually, such generalizations follow the original proof, while replacing the standard tools by their biased variants. This approach proved itself effective in many cases, but it requires to repeat the whole (sometimes lengthy) proof of the uniform case. In this talk we present a simple reduction which allows to transfrom some of the _statements_ from the uniform measure to the biased measure directly, without need to consider the proof. We apply the reduction to give extremely simple proofs of several known generalizations, and also present two new generalizations: A quantitative version of Friedgut's result on functions with a low sum of influences for a biased measure, and a biased version of Talagrand's lower bound on the size of the boundary of a subset of the discrete cube.

We prove that the fundamental group of a surface of genus >1 admits a dense embedding into the full symmetric group of a countable set. In other words, this group admits an action on a countable set that is transitive on ordered k-tuples for any k. This is done using a Bair category argument.

The partition function is a fundamental object in statistical mechanics from which probability distributions of various quantities can be derived. However, in most cases of interest it cannot be calculated, even for modest system sizes, due to complexity. An upscaling approach is presented in the context of glass-forming models, which enables one to approximate the partition function by replacing integrals in continuous variables with sums over a discrete set of upscaled states. At the heart of the approach is a simple criterion for verifying a proper choice of upscaled variables. The resulting solutions can be then utilized to predict the anomalously increasing time scales upon cooling.

Consider the random entire function $f(z) = \Sum^{\infty}_{n=0} \phi n \cdot a_n z^n$; where the  $\phi n$ are i.i.d. standard complex Gaussian variables, and $a_n$ are determinstic coe cients. We study the probability $P_H(r)$ that $f$ has no zeros in the disk $\{|z| 〈 r\}$ (hole probability). Under some regularity conditions for the $a_n$'s, we study the asymptotics of $P_H(r)$ for large values of $r$. More accurately, if we use the notation $S(r) = 2 \cdot \Sum_{n:a_n r^n \geq 1}log a_n r^n$; then we prove $log P_H(r) = S(r) + o (S(r))$ outside an exceptional (deterministic) set of $r$'s. Besides standard results from probability theory and complex analysis, the proof uses some parts of Wiman- Valiron theory.

Eviatar Procaccia
Mutual exited random walk

Consider two nearest neighbour random walkers on Z. The walkers are using the same clock. After two visits at a site, each walker leaves a drift p for the other walker. We prove the walkers have positive speed and the speed is non monotone in p.

Ron Rosenthal
Random walk on discrete point process

We will describe a model of random walk on random environment on a random subset of Z^d , with uniform transition probabilities on 2d points, two "nearest neighbors" in each of the d coordinate directions. We will than state that the velocity of such random walks is almost surely 0, and will discuss transience and recurrence classifications. Finally we will present a conjecture concerning CLT theorem for such random walks.

Eric Shellef
Percolation perspective on the random walk trace

Let T^d be the d-dimensional discrete torus of side N. Run a random walk for N^d steps in T^d and denote by R the set of vertices visited during this walk. With high probability, R is of size O(N^d) and its configuration inside T^d may be viewed as a dependent variant of iid site percolation in T^d. It is known that for supercritical iid site percolation, the largest connected cluster has diameter O(N) and mixing time O(N^2) with high probability. We use hierarchical renormalization to deal with the long-range dependence inherent in the our model, and prove a slightly weaker fact, that for any natural number k, diam(R) is o(Nlog(k)N) and the mixing time of a random walk on R is o(N^2log(k)N), where log(k) is log iterated k times.

Sasha Sodin
Band random matrices: the edge of the spectrum

We will try to explain what is a band matrix, how are its extremal eigenvalues distributed, and how is this related to the Thouless criterion and to the work of Fyodorov and Mirlin.

Yaar Solomon
Substitution tilings and separated nets with similarities to the integer lattice

We are dealing with tilings of Euclidean spaces and with the separated nets that they creates. When two separated nets are given, we study the question whether there is a biLipschitz bijection between them, or maybe even a bijection that translate the points a bounded distance. These conditions give rise to equivalence relations on the set of all separated nets, and we want to determine which separated nets falls to the equivalence class for Z^d. We give some background on tilings and some essential definitions of separated nets, and then present the results.

Omer Tamuz
Iterative maximum likelihood on networks

We consider $n$ agents located on the vertices of a connected graph. Each agent $v$ receives a signal $X_v(0)\sim N(\mu,1)$ where $\mu$ is an unknown quantity. A natural iterative way of estimating $\mu$ is to perform the following procedure. At iteration $t+1$ let $X_v(t+1)$ be the average of $X_v(t)$ and of $X_w(t)$ among all the neighbors $w$ of $v$. It is well known that this procedure converges to $X(\infty) = \frac{1}{2} |E|^{-1} \sum d_v X_v$ where $d_v$ is the degree of $v$.

Benjamin Weiss
A century of normal numbers

In 1909 E. Borel published his pioneering paper on denumerable probabilities in which he "showed" that almost every number $t \in [0,1]$ is absolutely normal. I will give an ergodic theoretic perspective on this result and relate it to the kollektiv of R. von Mises. If time permits I will also describe a stronger notion of normality that Y. Peres and I have studied. Here instead of the asymptotic frequency of blocks of a fixed size we are concerned with the distribution of blocks of growing size and convergence to a Poisson point process.