Arm exponents in high dimensional percolation (2009)
We study the probability that the origin is connected to the sphere of radius r (an arm event) in critical percolation in high dimensions, namely when the dimension d is large enough or when d>6 and...
Many Random Walks Are Faster Than One (2009)
Noga Alon, Chen Avin, Gady Kozma, Zvi Lotker, Mark R. Tuttle
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,...
One-dimensional long-range diffusion-limited aggregation I (2009)
Amir, Gideon, Angel, Omer, Benjamini, Itai, Kozma, Gady
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 moments a...
A note about critical percolation on finite graphs (2009)
In this note we study the geometry of the largest component C_1 of critical percolation on a finite graph G which satisfies the finite triangle condition, defined by Borgs et al. There it is shown...
Entropy of Random Walk Range (2009)
Benjamini, Itai, Kozma, Gady, Yadin, Ariel, Yehudayoff, Amir
We study the entropy of the set traced by an $n$-step random walk on $\Z^d$. We show that for $d \geq 3$, the entropy is of order $n$. For $d = 2$, the entropy is of order $n/\log^2 n$. These values...
The Alexander-Orbach conjecture holds in high dimensions (2008)
We examine the incipient infinite cluster (IIC) of critical percolation in regimes where mean-field behavior have been established, namely when the dimension d is large enough or when d>6 and the...
WAITING FOR A BAT TO FLY BY (IN POLYNOMIAL TIME) (2008)
Itai Benjamini, Gady Kozma, László Lovász, Dan Romik
Abstract. 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...
THE MINIMAL SPANNING TREE AND THE UPPER BOX DIMENSION (2008)
Gady Kozma, Zvi Lotker, Gideon Stupp
Abstract. We show that the α-weight of an MST over n points in a metric space with upper box dimension d has a bound independent of n if α>dand does not have one if α<d. 1.
Alea 3, 321–329 (2007) On the precision of the spectral profile (2008)
Abstract. We examine the spectral profile bound of Goel, Montenegro and Tetali for the L ∞ mixing time of continuous-time random walk in reversible settings. We find that it is precise up to a log...
MINERVA Center for Geometry at Tel Aviv University. (2007)
Gady Kozma, Zvi Lotker, Micha Sharir
Some of the first routing algorithms for geographically aware wireless networks used the Delaunay triangulation among the network’s nodes as the underlying connectivity graph [4]. These solutions...
On the precision of the spectral profile (2007)
We examine the spectral profile bound of Goel, Montenegro and Tetali for the uniform mixing time of continuous-time random walk in reversible settings. We find that it is precise up to a log log...
Kozma, Gady, Olevskii, Alexander
We examine the class of functions representable by an analytic sum converging almost everywhere. We show that this class is dense but that it is first category and has zero Wiener measure.
Many Random Walks Are Faster Than One (2007)
Alon, Noga, Avin, Chen, Koucky, Michal, Kozma, Gady, Lotker, Zvi, Tuttle, Mark R.
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,...
Kozma, Gady, Olevskii, Alexander
We examine the class of functions representable by an analytic sum converging almost everywhere. We show that this class is dense but that it is first category and has zero Wiener measure.
Kozma, Gady, Olevskii, Alexander
We examine the class of functions representable by an analytic sum converging almost everywhere. We show that this class is dense but that it is first category and has zero Wiener measure.
On the hyperplane conjecture for random convex sets (2006)
Let N > n, and denote by K the convex hull of N independent standard gaussian random vectors in an n-dimensional Euclidean space. We prove that with high probability, the isotropic constant of K is...
One cannot hear the winding number (2006)
We construct an example of two continuous maps f and g of the circle to itself with the same absolute value of the Fourier transform but with different winding numbers, answering a question of Brezis.
Anomalous heat-kernel decay for random walk among bounded random conductances (2006)
Berger, Noam, Biskup, Marek, Hoffman, Christopher E., Kozma, Gady
We consider the nearest-neighbor simple random walk on $\Z^d$, $d\ge2$, driven by a field of bounded random conductances $\omega_{xy}\in[0,1]$. The conductance law is i.i.d. subject to the condition...
Analytic representation of functions and a new quasi-analyticity threshold (2006)
Kozma, Gady, Olevskiĭ, Alexander
We characterize precisely the possible rate of decay of the anti-analytic half of a trigonometric series converging to zero almost everywhere.
The mixing time of the giant component of a random graph (2006)
Benjamini, Itai, Kozma, Gady, Wormald, Nicholas
We show that the total variation mixing time of the simple random walk on the giant component of supercritical Erdos-Renyi graphs is log^2 n. This statement was only recently proved, independently,...
Random walks with k-wise independent increments (2006)
Benjamini, Itai; The Weizmann Institute Of Science; Itai@wisdom.weizmann.ac.il, Kozma, Gady; The Weizmann Institute Of Science; Gady@ias.edu, Romik, Dan; University Of California, Berkeley; Romik@stat.berkeley.edu
We construct examples of a random walk with pairwise-independent steps which is almost surely bounded, and for any m and k a random walk with k-wise independent steps which has no stationary...
On the connectivity of the Poisson process on fractals (2006)
Kozma, Gady, Lotker, Zvi, Stupp, Gideon
For a measure mu supported on a compact connected subset of a Euclidean space which satisfies a uniform d-dimensional decay of the volume of balls we show that the maximal edge in the minimum...
On the gaps between zeros of trigonometric polynomials (2006)
We show that for every finite symetric set S of integer vectors, every real trigonometric polynomial on the d dimensional torus with spectrum in S has a zero in every closed ball of diameter D, where...
Analytic representation of functions and a new quasi-analyticity threshold (2006)
Kozma, Gady, Olevskii, Alexander
We characterize precisely the possible rate of decay of the anti-analytic half of a trigonometric series converging to zero almost everywhere.
Excited random walk in two dimensions has linear speed (2005)
Excited random walk is a process that has a drift to the right whenever it encounters a new vertex. The paper shows that in two dimensions it drifts to the right linearly in time.
Kozma, Gady, Olevskii, Alexander
Inspired by Menshov's representation theorem, we prove that there exists a sequence of frequecies such that any measurable (complex valued) function on R can be represented as a sum of almost...
An "Analytic" Version of Menshov's Representation Theorem (2005)
Kozma, Gady, Olevskii, Alexander
Every measurable function f on the circle can be represented as a sum of harmonics with positive spectrum, converging in measure. For convergence almost everywhere this is not true. We discuss...
Random homeomorphisms and Fourier expansions - the pointwise behavior (2005)
Let phi be a Dubins-Freedman random homeomorphism on [0,1] derived from the base measure uniform on the vertical line x=1/2, and let f be a periodic function satisfying that |f(x)-f(0)| = o(1/log log...
Menshov representation spectra (2005)
Kozma, Gady, Olevskii, Alexander
A Menshov spectrum is a subset of the integers that is sufficient for representing every measurable function as an almost-everywhere converging trigonometric (non-Fourier) sum. In this language the...
Kozma, Gady, Olevskii, Alexander
We show that a spectrum of frequencies obtained by a random perturbation of the integers allows one to represent any measurable function on R by an almost everywhere converging sum of harmonics...
Maximal smoothness of the anti-analytic part of a trigonometric null series (2005)
Kozma, Gady, Olevskii, Alexander
We proved recently math.CA/0510403 that the anti-analytic part of a trigonometric series, converging to zero almost everywhere, may be square integrable on the circle. Here we prove that it can even...
A null series with small anti-analytic part (2005)
Kozma, Gady, Olevskii, Alexander
We show that it is possible for a square integrable function on the circle, which is a sum of an almost everywhere convergent series of exponentials with positive frequencies, to not belong to the...
Kozma, Gady, Olevskii, Alexander
We examine the class of functions representable by an analytic sum (by which we mean a trigonometric sum involving only positive frequencies) converging almost everywhere. We show that it is dense...
Excited random walk against a wall (2005)
Amir, Gideon, Benjamini, Itai, Kozma, Gady
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...
Percolation, Perimetry, Planarity (2005)
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
The scaling limit of loop-erased random walk in three dimensions (2005)
We show that the scaling limit exists and is invariant to dilations and rotations. We give some tools that might be useful to show universality.
On removing one point from a compact space (2005)
If B is a compact space and B\{pt} is Lindelof then B^k\{pt} is star-Linedlof for every cardinality k. If B\{pt} is compact then B^k\{pt} is discretely star-Lindelof. In particular, this gives new...
Analytic representation of functions and a new quasi-analyticity threshold (2004)
Kozma, Gady, Olevskii, Alexander
We characterize precisely the possible rate of decay of the anti-analytic half of a trigonometric series converging to zero almost everywhere.
Random walks with $k$-wise independent increments (2004)
Benjamini, Itai, Kozma, Gady, Romik, Dan
We construct examples of a random walk with pairwise-independent steps which is almost-surely bounded, and for any $m$ and $k$ a random walk with $k$-wise independent steps which has no stationary...
An asymptotic expansion for the discrete harmonic potential (2004)
Kozma, Gady; Tel Aviv University; Gadykozma@hotmail.com, Schreiber, Ehud; Tel Aviv University; Schreib@physics.ubc.ca
We give two algorithms that allow to get arbitrary precision asymptotics for the harmonic potential of a random walk.
The minimal spanning tree and the upper box dimension (2003)
Kozma, Gady, Lotker, Zvi, Stupp, Gideon
We show that the alpha-weight of an MST over n points in a metric space with upper box dimension d has a bound independent of n if alpha is smaller than d and does not have one if alpha is larger...
Waiting for a bat to fly by (in polynomial time) (2003)
Benjamini, Itai, Kozma, Gady, Lovasz, Laszlo, Romik, Dan, Tardos, Gabor
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...
Excited random walk in three dimensions has positive speed (2003)
Excited random walk is a random walk that has a positive drift to the right when it reaches a vertex it hasn't been to before. We show that in three dimensions the walk drifts to the right in...
Loop-erased random walk on a torus in dimensions 4 and above (2003)
Sharp estimates for the length of loop erased random walk between two vertices on the [n]^d -torus, d > 4, are established. The mean length is order n^{d/2} . In dimension 4 we have only an upper...
Scaling limit of loop erased random walk - a naive approach (2002)
We give an alternative proof of the existence of the scaling limit of loop erased random walk which does not use Lowner's differential equation.
A Resistance Bound via an Isoperimetric Inequality (2002)
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...
An asymptotic expansion for the discrete harmonic potential (2002)
We give two algorithms that allow to get arbitrary precision asymptotics for the harmonic potential of a random walk.