Publications

Let f be sampled uniformly at random from the set of degree n polynomials whose coefficients lie in {±1}. A folklore conjecture, known to hold under GRH, states that the probability that f is irreducible tends to 1 as n goes to infinity. We prove unconditionally that (Formula presented).

We prove that for ℤ^d (d ≥ 2), the vertex-removal stability of harmonic measures (i.e., it is feasible to remove some vertex while changing the harmonic measure by a bounded factor) holds if and only if d = 2. The proof mainly relies on geometric arguments, with a surprising use of the discrete Klein bottle. Moreover, a direct application of this stability verifies a conjecture of Calvert, Ganguly and Hammond (Forum Math. Sigma 11 (2023) 72) for the exponential decay of the least positive value of harmonic measures on ℤ². Furthermore, the analogue of this conjecture for ℤ^d with d ≥ 3 is also proved in this paper, despite vertex-removal stability no longer holding.

In their celebrated paper [CLR10], Caputo, Liggett and Richthammer proved Aldous conjecture and showed that for an arbitrary finite graph, the spectral gap of the interchange process is equal to the spectral gap of the underlying random walk. A crucial ingredient in the proof was the Octopus Inequality a certain inequality of operators in the group ring R ^`Sym_n of the symmetric group. Here we generalise the Octopus Inequality and apply it to generalising the CaputoLiggettRichthammer Theorem to certain hypergraphs, proving some cases of a conjecture of Caputo.

We prove that all groups of exponential growth support non-constant positive harmonic functions. In fact, our results hold in the more general case of strongly connected, finitely supported Markov chains invariant under some transitive group of automorphisms for which the directed balls grow exponentially.

We prove that every locally finite vertex -transitive graph G admits a non -constant Lipschitz harmonic function.

The collection M_n of all metric spaces on n points whose diameter is at most 2 can naturally be viewed as a compact convex subset of R ⁽ⁿ2 ⁾ , known as the metric polytope. In this paper, we study the metric polytope for large n and show that it is close to the cube [1, 2] ⁽ⁿ2 ⁾ ⊆ M_n in the following two senses. First, the volume of the polytope is not much larger than that of the cube, with the following quantitative estimates: ⁽₆¹ + o(1) ) n^3/2 ≤ log Vol(M_n) ≤ O(n^3/2). Second, when sampling a metric space from M_n uniformly at random, the minimum distance is at least 1 − n^−c with high probability, for some c > 0. Our proof is based on entropy techniques. We discuss alternative approaches to estimating the volume of M_n using exchangeability, Szemerédis regularity lemma, the hypergraph container method, and the KőváriSósTurán theorem.

For any order of growth f (n) = o(log n), we construct a finitely-generated group G and a set of generators S such that the Cayley graph of G with respect to S supports a harmonic function with growth f but does not support any harmonic function with slower growth. The construction uses permutational wreath products Z/2 ≀_X Γ in which the base group Γ is defined via its properly chosen action on X .

Let μ be a probability measure on ℤ that is not a Dirac mass and that has finite support. We prove that if the coefficients of a monic polynomial f(x) ∈ Z[x] of degree n are chosen independently at random according to μ while ensuring that f(0) ≠ 0 , then there is a positive constant θ= θ(μ) such that f(x) has no divisors of degree ≤ θn with probability that tends to 1 as n→ ∞ . Furthermore, in certain cases, we show that a random polynomial f(x) with f(0) ≠ 0 is irreducible with probability tending to 1 as n→ ∞ . In particular, this is the case if μ is the uniform measure on a set of at least 35 consecutive integers, or on a subset of [− H, H] ∩ Z of cardinality ≥ H^{4 / 5}(log H) ² with H sufficiently large. In addition, in all of these settings, we show that the Galois group of f(x) is either A_n or S_n with high probability. Finally, when μ is the uniform measure on a finite arithmetic progression of at least two elements, we prove a random polynomial f(x) as above is irreducible with probability ≥ δ for some constant δ= δ(μ) > 0 . In fact, if the arithmetic progression has step 1, we prove the stronger result that the Galois group of f(x) is A_n or S_n with probability ≥ δ .

We show that the total variation mixing time is not quasi-isometry invariant, even for Cayley graphs. Namely, we construct a sequence of pairs of Cayley graphs with maps between them that twist the metric in a bounded way, while the ratio of the two mixing times goes to infinity. The Cayley graphs serving as an example have unbounded degrees. For non-transitive graphs we construct bounded degree graphs for which the mixing time from the worst starting point for one graph is asymptotically smaller than the mixing time from the best starting point of the random walk on a network obtained by increasing some of the edge weights from 1 to 1 + o(1).

We survey our recent result that for every continuous function there is an absolutely continuous homeomorphism such that the composition has a uniformly converging Fourier expansion. We mention the history of the problem, orginally stated by Luzin, and some details of the proof.

We study the fire-retaining problem on groups, a quasi-isometry invariant¹ introduced by Martínez-Pedroza and Prytuła [8], related to the firefighter problem. We prove that any Cayley graph with degree-d polynomial growth does not satisfy {f(n)}-retainment, for any f(n)=o(n^d−2), matching the upper bound given for the firefighter problem for these graphs. In the exponential growth regime we prove general lower bounds for direct products and wreath products. These bounds are tight, and show that for exponential-growth groups a wide variety of behaviors is possible. In particular, we construct, for any d≥1, groups that satisfy {n^d}-retainment but not o(n^d)-retainment, as well as groups that do not satisfy sub-exponential retainment.

We show that there exists a bounded subset of R such that no system of exponentials can be a Riesz basis for the corresponding Hilbert space. An additional result gives a lower bound for the Riesz constant of any putative Riesz basis of the two-dimensional disk.

We show that the naive mean-field approximation correctly predicts the leading term of the logarithmic lower tail probabilities for the number of copies of a given subgraph in G(n,p) and of arithmetic progressions of a given length in random subsets of the integers in the entire range of densities where the mean-field approximation is viable. Our main technical result provides sufficient conditions on the maximum degrees of a uniform hypergraph H that guarantee that the logarithmic lower tail probabilities for the number of edges, induced by a binomial random subset of the vertices of H, can be well approximated by considering only product distributions. This may be interpreted as a weak, probabilistic version of the hypergraph container lemma that is applicable to all sparser-than-average (and not only independent) sets.

Abstract: We show that for every continuous function f there exists an absolutely continuous circle homeomorphism φ such that the Fourier series of f ◦ φ converges uniformly. This resolves a problem posed by N. N. Luzin.

We introduce the notion of Random Walk in Changing Environment (RWCE) a random walk on a weighted graph in which the weights may change between steps. RWCE's generalize many known RW (e.g. reinforced RW, true SAW). We explore possible properties of RWCE's, and provide criteria for recurrence and transience when the underlying graph is N or a tree. We construct a RWCE on Z² where conductances can only change from 1 to 2 (once) but nevertheless the walk is transient, and conjecture that such behavior cannot happen when the changes do not depend on the location of the RWCE.

We prove that any Cayley graph G with degree d polynomial growth does not satisfy {f(n)}-containment for any f=o(n^d−2). This settles the asymptotic behaviour of the firefighter problem on such graphs as it was known that Cn^d−2 firefighters are enough, answering and strengthening a conjecture of Develin and Hartke. We also prove that intermediate growth Cayley graphs do not satisfy polynomial containment, and give explicit lower bounds depending on the growth rate of the group. These bounds can be further improved when more geometric information is available, such as for Grigorchuk's group.

Operator inequalities with a geometric flavour have been successful in studying mixing of random walks and quantum mechanics. We suggest a new way to extract such inequalities using the octopus inequality of Caputo, Liggett and Richthammer.

It is shown that the trace of three dimensional Brownian motion contains arithmetic progressions of length 5 and no arithmetic progressions of length 6 a.s.

We consider a one dimensional interacting particle system which describes the effective interface dynamics of the two dimensional Toom model at low noise. We prove a number of basic properties of this model. First we consider the dynamics on a finite interval [1, N) and bound the mixing time from above by 2N. Then we consider the model defined on the integers. Because the interaction range of the rates and the jump sizes can be arbitrarily large, this is a non-Feller process. As such, we can define the process starting from product Bernoulli measures with density p is an element of(0,1), but not from arbitrary measures. We show that the only possible invariant measures are those product Bernoulli measures, under a modest technical condition. We further show that the unique stationary measure on [0,infinity) converges to a product Bernoulli measure with fixed density when viewed far from 0.

The goal of this paper is to prove that a random polynomial with independent and identically distributed random coefficients taking values uniformly in {1;::: ; 210} is irreducible with probability tending to 1 as the degree tends to infinity. Moreover, we prove that the Galois group of the random polynomial contains the alternating group, again with probability tending to 1.

We study internal diffusion-limited aggregation with uniform starting points on Z(d). In this model, each new particle starts from a vertex chosen uniformly at random on the existing aggregate. We prove that the limiting shape of the aggregate is a Euclidean ball.

We show that for a fixed k is an element of N, Gromov random groups with any density d > 0 have no nontrivial degree k representations over any field, a.a.s. This is especially interesting in light of the results of Agol, Ollivier and Wise that when d

Consider the graph obtained by superposition of an independent pair of uniform infinite non-crossing perfect matchings of the set of integers. We prove that this graph contains at most one infinite path. Several motivations are discussed.

We study bond percolation on the square lattice with one-dimensional inhomogeneities. Inhomogeneities are introduced in the following way: A vertical column on the square lattice is the set of vertical edges that project to the same vertex on Z. Select vertical columns at random independently with a given positive probability. Keep (respectively remove) vertical edges in the selected columns, with probability p (respectively 1-p). All horizontal edges and vertical edges lying in unselected columns are kept (respectively removed) with probability q (respectively 1 - q). We show that, if p > p (c)(Z (2)) (the critical point for homogeneous Bernoulli bond percolation), then q can be taken strictly smaller than p (c)(Z (2)) in such a way that the probability that the origin percolates is still positive.

We show Green's function asymptotic upper bound for the two-point function of weakly self-Avoiding walk in d >4, revisiting a classic problem. Our proof relies on Banach algebras to analyse the lace-expansion fixed point equation and is simpler than previous approaches in that it avoids Fourier transforms.

We prove a central limit theorem under diffusive scaling for the displacement of a random walk on Z(d) in stationary and ergodic doubly stochastic random environment, under the H-1-condition imposed on the drift field. The condition is equivalent to assuming that the stream tensor of the drift field be stationary and square integrable. This improves the best existing result [Fluctuations in Markov Processes-Time Symmetry and Martingale Approximation (2012) Springer], where it is assumed that the stream tensor is in L-max{2+delta,L-d}, with delta > 0. Our proof relies on an extension of the relaxed sector condition of [Bull. Inst. Math. Acad. Sin. (N. S.) 7 (2012) 463-476], and is technically rather simpler than existing earlier proofs of similar results by Oelschlager [Ann. Probab. 16 (1988) 1084-1126] and Komorowski, Landim and Olla [Fluctuations in Markov Processes-Time Symmetry and Martingale Approximation (2012) Springer].

We study the O(n) model on graphs quasi-isometric to the hyperbolic plane, with free boundary conditions. We observe that the pair correlation decays exponentially with distance, for all temperatures, if and only if n> 1.

We study the minimal possible growth of harmonic functions on lamplighters. We find that (Z/2) (Formula presented.) Z² has no sublinear harmonic functions, (Z/2) (Formula presented.) Z² has no sublogarithmic harmonic functions, and neither has the repeated wreath product ( (Z/2 (Formula presented.) Z²) (Formula presented.) Z²) (Formula presented.) (Symbol found) Z². These results have implications on attempts to quantify the Derriennic-Kaimanovich-Vershik theorem.

We examine diffusion-limited aggregation for a one-dimensional random walk with long jumps.We achieve upper and lower bounds on the growth rate of the aggregate as a function of the number of moments a single step of the walk has. In this paper, we handle the case of transient walks.

We prove that every finite union of rectangles with edges parallel to the axes in ℝ^d admits a Riesz basis of exponentials.

We prove that the probability of a random polynomial in two variables of degree n and with ± 1 coefficients to be irreducible tends to 1 as n → ∞.

In this paper we consider an excited random walk (ERW) on Z in identically piled periodic environment. This is a discrete time process on Z defined by parameters (p1,..., pM) ∈ [0, 1]M for some positive integer M, where the walker upon the ith visit to z ∈ Z moves to z + 1 with probability pi (mod M), and moves to z - 1 with probability 1 - pi (mod M). We give an explicit formula in terms of the parameters (p1,..., pM) which determines whether the walk is recurrent, transient to the left, or transient to the right. In particular, in the case that 1/M Σ^mi=1 pi = 1/2 all behaviors are possible, and may depend on the order of the pi. Our framework allows us to reprove some known results on ERW and branching processes with migration with no additional effort.

We study a natural discrete Bochner-type inequality on graphs, and explore its merit as a notion of "curvature" in discrete spaces. An appealing feature of this discrete version of the so-called Γ₂-calculus (of Bakry-Émery) seems to be that it is fairly straightforward to compute this notion of curvature parameter for several specific graphs of interest, particularly, abelian groups, slices of the hypercube, and the symmetric group under various sets of generators. We further develop this notion by deriving Buser-type inequalities (à la Ledoux), relating functional and isoperimetric constants associated with a graph. Our derivations provide a tight bound on the Cheeger constant (i.e., the edge-isoperimetric constant) in terms of the spectral gap, for graphs with nonnegative curvature, particularly, the class of abelian Cayley graphs, a result of independent interest.

We provide new bounds for the divisibility function of the free group F₂ and construct short laws for the symmetric groups Sym(n). The construction is random and relies on the classification of the finite simple groups. We also give bounds on the length of laws for finite simple groups of Lie type.

We examine diffusion-limited aggregation generated by a random walk on Z; with long jumps. We derive upper and lower bounds on the growth rate of the aggregate as a function of the number of moments a single step of the walk has. Under various regularity conditions on the tail of the step distribution, we prove that the diameter grows as n^β+o(1), with an explicitly given β. The growth rate of the aggregate is shown to have three phase transitions, when the walk steps have finite third moment, finite variance, and conjecturally, finite half moment.

We show that in the Lorentz mirror model, at any density of mirrors, (Formula Presented.).

We show that in high dimensional Bernoulli bond percolation, removing from a thin infinite cluster a much thinner infinite cluster leaves an infinite component. This observation has implications for the van den Berg-Brouwer forest fire process, also known as self-destructive percolation, for dimension high enough.

Consider the process of random transpositions on the complete graph Kn. We use representation theory to give an exact, simple formula for the expected number of cycles of size k at time t, in terms of an incomplete Beta function. Using this we show that the expected number of cycles of size k jumps from 0 to its equilibrium value, 1=k, at the time where the giant component of the associated random graph first exceeds k. Consequently we deduce a new and simple proof of Schramm's theorem on random transpositions, that giant cycles emerge at the same time as the giant component in the random graph. We also calculate the "window" for this transition and find that it is quite thin. Finally, we give a new proof of a result by the first author and Durrett that the random transposition process exhibits a certain slowdown transition. The proof makes use of a recent formula for the character decomposition of the number of cycles of a given size in a permutation, and the Frobenius formula for the character ratios.

We study harmonic functions on random environments with particular emphasis on the case of the infinite cluster of supercritical percolation on Zd. We prove that the vector space of harmonic functions growing at most linearly is (d + 1)-dimensional almost surely. Further, there are no nonconstant sublinear harmonic functions (thus implying the uniqueness of the corrector). A main ingredient of the proof is a quantitative, annealed version of the Avez entropy argument. This also provides bounds on the derivative of the heat kernel, simplifying and generalizing existing results. The argument applies to many different environments; even reversibility is not necessary.

We show that the total variation mixing time of the simple random walk on the giant component of supercritical G(n,p) and G(n,m) is Theta(log(2) n). This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are "decorated expanders" - an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. (C) 2014 Wiley Periodicals, Inc.

We prove that vertex-reinforced random walk on Z with weight of order k^α, for α∈[0, 1/2), is recurrent. This confirms a conjecture of Volkov for α

In this article, we consider the following model of self-avoiding walk: the probability of a self-avoiding trajectory γ between two points on the boundary of a finite subdomain of ℤ is proportional to μ ^-length (γ). When μ is supercritical (i.e. μ c where μ_c is the connective constant of the lattice), we show that the random trajectory becomes space-filling when taking the scaling limit.

We prove that the linearly edge reinforced random walk (LRRW) on any graph with bounded degrees is recurrent for sufficiently small initial weights. In contrast, we show that for nonamenable graphs the LRRW is transient for sufficiently large initial weights, thereby establishing a phase transition for the LRRW on nonamenable graphs. While we rely on the equivalence of the LRRW to a mixture of Markov chains, the proof does not use the so-called magic formula which is central to most work on this model. We also derive analogous results for the vertex reinforced jump process.

Two related issues are explored for bond percolation on ℤ^d (with d ≥ 3) and its dual plaquette process. Firstly, for what values of the parameter p does the complement of the infinite open cluster possess an infinite component? The corresponding critical point p fin satisfies p fin ≥ p _c, and strict inequality is proved when either d is sufficiently large, or d ≥ 7 and the model is sufficiently spread out. It is not known whether d ≥ 3 suffices. Secondly, for what p does there exist an infinite dual surface of plaquettes? The associated critical point p surf satisfies p surf ≥ p fin.

There exists a graph with two vertices x and y such that the ratio of the heat kernels p(x, x; t)/p(y, y; t) does not converge as t→∞.

We show that any finite union of intervals supports a Riesz basis of exponentials.

A dyadic tile of order n is any rectangle obtained from the unit square by n successive bisections by horizontal or vertical cuts. Let each dyadic tile of order n be available with probability p, independent of the others. We prove that for p sufficiently close to 1, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to 1 as n→∞, as conjectured by Joel Spencer in 1999. In particular, we prove that if p = 7/8, such a tiling exists with probability at least 1 - (3/4)ⁿ. The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.

We proved earlier that every measurable function on the circle, after a uniformly small perturbation, can be written as a power series (i.e., a series of exponentials with positive frequencies), which converges almost everywhere. Here, we show that this result is basically sharp: the perturbation cannot be made smooth or even Hölder. We also discuss a similar problem for perturbations with lacunary spectrum.

We examine the number of cycles of length k in a permutation as a function on the symmetric group. We write it explicitly as a combination of characters of irreducible representations. This allows us to study the formation of long cycles in the interchange process, including a precise formula for the probability that the permutation is one long cycle at a given time t , and estimates for the cases of shorter cycles.

We show that there exists a connected graph G with subexponential volume growth such that critical percolation on G × ℤ has infinitely many infinite clusters. We also give some conditions under which this cannot occur.

Inspired by Aldous' conjecture for the spectral gap of the interchange process and its recent resolution by Caputo, Liggett, and Richthammer, we define an associated order on the irreducible representations of Sn. Aldous' conjecture is equivalent to certain representations being comparable in this order, and hence determining the 'Aldous order' completely is a generalized question. We show a few additional entries for this order.

We study the "Fourier symmetry" of measures and distributions on the circle, in relation with the size of their supports. The main results of this paper are: (i) A one-side extension of Frostman's theorem, which connects the rate of decay of Fourier transform of a distribution with the Hausdorff dimension of its support; (ii) A construction of compacts of "critical" size, which support distributions (even pseudo-functions) with anti-analytic part belonging to l². We also give examples of non-symmetry which may occur for measures with "small" support. A number of open questions are stated.

In this note we study the geometry of the largest component C₁of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. (Random Struct. Algorithms 27:137-184, 2005). There it is shown that this component is of size n^2/3, and here we show that its diameter is n^1/3 and that the simple random walk takes n steps to mix on it. By Borgs et al. (Ann. Probab. 33:1886-1944, 2005), our results apply to critical percolation on several high-dimensional finite graphs such as the finite torus ℤ^d_n(with d large and n→∞) and the Hamming cube {0,1}ⁿ.

We study the basis property of systems of exponentials with frequencies belonging to 'simple quasicrystals'. We show that a diophantine condition is necessary and sufficient for such a system to be a Riesz basis in L² on a finite union of intervals. For the proof we extend to BMO a theorem of Kesten about the discrepancy of irrational rotations of the circle.

We show that critical percolation on a product of two regular trees of degree ≥ 3 satisfies the triangle condition. The proof does not examine the degrees of vertices and is not "perturbative" in any sense. It relies on an unpublished lemma of Oded Schramm.

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

The following random process on Z⁴ is studied. At first visit to a site, the two first coordinates perform a (2-dimensional) simple random walk step. At further visits, it is the last two coordinates which perform a simple random walk step. We prove that this process is almost surely transient. The lower dimensional versions are discussed and various generalizations and related questions are proposed.

We show that for percolation on any transitive graph, the triangle condition implies the open triangle condition.

We study the Laplacian-∞ path as an extreme case of the Laplacian-α random walk. Although, in the finite α case, there is reason to believe that the process converges to SLE _κ, with κ = 6/(2α + 1), we show that this is not the case when α = ∞ In fact, the scaling limit depends heavily on the lattice structure, and is not conformal (or even rotational) invariant.

We study the entropy of the set traced by an n-step simple symmetric random walk on ℤ^d . We show that for d ≥ 3, the entropy is of order n. For d = 2, the entropy is of order n/ log² n. These values are essentially governed by the size of the boundary of the trace.

Let μ be a measure supported on a compact connected subset of an Euclidean space, which satisfies a uniform d-dimensional decay of the volume of balls of the type(1)α δ^d ≤ μ (B (x, δ)) ≤ β δ^d where d is a fixed constant. We show that the maximal edge in the minimum spanning tree of n independent samples from μ is, with high probability ≈ (frac(log n, n))^{1 / d}. While previous studies on the maximal edge of the minimum spanning tree attempted to obtain the exact asymptotic, we on the other hand are interested only on the asymptotic up to multiplication by a constant. This allows us to obtain a more general and simpler proof than previous ones.

We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior has been established, namely when the dimension d is large enough or when d > 6 and the lattice is sufficiently spread out. We find that random walk on the IIC exhibits anomalous diffusion with the spectral dimension, that is, p_t(x,x)=t^-2/3+o(1). This establishes a conjecture of Alexander and Orbach (J. Phys. Lett. (Paris) 43:625-631, 1982). En route we calculate the one-arm exponent with respect to the intrinsic distance.

Let N ≥ n + 1, and denote by K the convex hull of N independent standard gaussian random vectors in ℝ ⁿ. We prove that with high probability, the isotropic constant of K is bounded by a universal constant. Thus we verify the hyperplane conjecture for the class of gaussian random polytopes.

We consider the nearest-neighbor simple random walk on ℤ^d , d ≥ 2, driven by a field of bounded random conductances ω_xy ∞ [0, 1]. The conductance law is i.i.d. subject to the condition that the probability of ω_xy > 0 exceeds the threshold for bond percolation on ℤ^d . For environments in which the origin is connected to infinity by bonds with positive conductances, we study the decay of the 2n-step return probability P_ω²ⁿ (0, 0) .We prove that P_ω²ⁿ (0, 0) is bounded by a random constant times n ^-d/2 in d = 2, 3, while it is o(n ^-2) in d ≥ 5 andO(n ^-2 log n) in d = 4. By producing examples with anomalous heat-kernel decay approaching 1/n², we prove that the o(n ^-2) bound in d ≥ 5 is the best possible. We also construct natural n-dependent environments that exhibit the extra log n factor in d = 4.

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time-the expected time required to visit every node in a graph at least once-and we show that for a large collection of interesting graphs, running many random walks in parallel jdelds a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probabilistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected fit-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

We analyze random walk in the upper half of a three-dimensional lattice which goes down whenever it encounters a new vertex, a.k.a. excited random walk. We show that it is recurrent with an expected number of returns of √log t.

We examine the class of functions representable by an analytic sum f (t)= ∑_n≥0 c(n)eint converging almost everywhere. We show that this class is dense but that it is first category and has zero Wiener measure.

We construct an example of two continuous maps f and g of the circle to itself with | f̂ (n)| = |ĝ(n)| for all n ∈ ℤ but with different winding numbers, answering a question of Brezis.

Let G be a planar graph with polynomial growth and isoperimetric dimension bigger than 1. Then the critical p for Bernoulli percolation on G satisfies p_c

We characterize precisely the possible rate of decay of the anti-analytic half of a trigonometric series converging to zero almost everywhere.

We observe returns of a simple random walk on a finite graph to a fixed node, and would like to infer properties of the graph, in particular properties of the spectrum of the transition matrix. This is not possible in general, but at least the set of eigenvalues can be recovered under fairly general conditions, e.g., when the graph has a node-transitive automorphism group. The main result is that by observing polynomially many returns, it is possible to estimate the spectral gap of such a graph up to a constant factor.

We construct examples of a random walk with pairwise-independent steps which is almostsurely bounded, and for any m and k a random walk with k-wise independent steps which has no stationary distribution modulo m.

An isoperimetric upper bound on the resistance is given. As a corollary we resolve two problems, regarding mean commute time on finite graphs and resistance on percolation clusters. Further conjectures are presented.

We show that the statistics of loop erased random walks above the upper critical dimension, 4, are different between the torus and the full space. The typical length of the path connecting a pair of sites at distance L, which scales as L ² in the full space, changes under the periodic boundary conditions to L ^d/2. The results are precise for dimensions ≥ 5; for the dimension d=4 we prove an upper bound, conjecturally sharp up to subpolyonmial factors.

Some of the first routing algorithms for position-aware wireless networks used the Delaunay triangulation of the point-locations of the network's nodes as the underlying connectivity graph. Later on these solutions were considered impractical because the Delaunay triangulation may in general contain arbitrarily long edges and because calculating the Delaunay triangulation may require a global view of the network. Many other algorithms were then suggested for geometric routing, often assuming random placement of network nodes for analysis or simulation [27, 5, 28, 15]. But as we show, when the nodes are uniformly placed in the unit disk the Delaunay triangulation does not contain long edges, it is easy to compute locally and it is in many ways optimal for geometric routing and flooding. In particular, we prove that with high probability the maximal length of an edge in Del(P), the Delaunay triangulation of a set P of n nodes uniformly placed in the unit disk, is O (3√log n/n), and that the expected sum of squares of all the edges in Del(P) is O(1). These geometric results imply that for wireless networks, randomly distributed in a unit disk (1) computing the Delaunay triangulation locally is asymptotically easy; (2) simple "face routing" through the Delaunay triangulation optimizes, up to poly-logarithmic factors, the energy load on the nodes, and (3) flooding the network, an operation quite common in sensor nets, is with high probability optimal up to a constant factor. The last property is particularly important for geocasting because the Delaunay triangulation is known to be a spanner.

Let φ be a Dubins-Freedman random homeomorphism on [0, 1] derived from the base measure uniform on {x = 1/2}, and let f be a periodic function satisfying |f(δ) - f(0)| = o(log log log 1/δ)^-1. Then the Fourier expansion of f ο Φ converges at 0 with probability 1. In the condition on f, o cannot be replaced by O. Also we deduce some 0-1 laws for this kind of problem.

If B is a compact space and B \ {pt} is Lindelöf then B ^κ \ {→pt} is star-Linedlöf for every κ. If B \ {pt} is compact then Bκ \ {→pt} is discretely star-Lindelo̧f. In particular, this gives new examples of Tychonoff discretely star-Lindelöf spaces with unlimited extent.

We show that the spectra λ of frequencies λ obtained by random perturbations of the integers allows one to represent any measurable function f on ℝ by an almost everywhere converging sum of harmonics: f = ∑c_λe^iλt.

We show that it is possible for an L² function on the circle, which is a sum of an almost everywhere convergent series of exponentials with positive frequencies, to not belong to the Hardy space H². A consequence in the uniqueness theory is obtained.

We show that for every finite set 0 ∉ S ⊂ ℤ^d with the property -S = S, every real trigonometric polynomial f on the d dimensional torus T^d = ℝ^d /ℤ^d with spectrum in S has a zero in every closed ball of diameter D (S), where D (S) and investigate tightness in some special cases.