Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness (2009)
Ben-Eliezer, Ido, Lovett, Shachar, Yadin, Ariel
We study the computational power of polynomial threshold functions, that is, threshold functions of real polynomials over the boolean cube. We provide two new results bounding the computational power...
Rate of Escape of the Mixer Chain (2009)
Yadin, Ariel; Weizmann Institute; Ariel.yadin@weizmann.ac.il
The mixer chain on a graph G is the following Markov chain. Place tiles on the vertices of G, each tile labeled by its corresponding vertex. A "mixer" moves randomly on the graph, at each step either...
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...
Ronen Gradwohl, Omer Reingold, Ariel Yadin, Amir Yehudayoff
In a function that takes its inputs from various players, the effect of a player mea-sures the variation he can cause in the expectation of that function. In this paper we prove a tight upper bound...
Loop-Erased Random Walk and Poisson Kernel on Planar Graphs (2008)
Yadin, Ariel, Yehudayoff, Amir
Lawler, Schramm and Werner showed that the scaling limit of the loop-erased random walk on the square lattice is SLE(2). We consider scaling limits of the loop-erasure of random walks on other planar...
Gradwohl, Ronen, Reingold, Omer, Yadin, Ariel, Yehudayoff, Amir
In a function that takes its inputs from various players, the effect of a player measures the variation he can cause in the expectation of that function. In this paper we prove a tight upper bound on...
The Maximal Probability that k-wise Independent Bits are All 1 (2007)
Peled, Ron, Yadin, Ariel, Yehudayoff, Amir
A k-wise independent distribution on n bits is a joint distribution of the bits such that each k of them are independent. In this paper we consider k-wise independent distributions with identical...
When Do Random Subsets Decompose a Finite Group? (2007)
Let A,B be two random subsets of a finite group G. We consider the event that the products of elements from A and B span the whole group; i.e. (AB union BA) = G. The study of this event gives rise to...
Maximal Arithmetic Progressions in Random Subsets (2007)
Benjamini, Itai; Weizmann Institute Of Science; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute Of Science; Ariel.yadin@weizmann.ac.il, Zeitouni, Ofer; University Of Minnesota; Zeitouni@math.umn.edu
Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to...
Maximal Arithmetic Progressions in Random Subsets (2007)
Benjamini, Itai, Yadin, Ariel, Zeitouni, Ofer
Let U(N) denote the maximal length of arithmetic progressions in a random uniform subset of {0,1}^N. By an application of the Chen-Stein method, we show that U(N)- 2 log(N)/log(2) converges in law to...
Random Graph-Homomorphisms and Logarithmic Degree (2007)
Benjamini, Itai; Weizmann Institute; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute; Ariel.yadin@weizmann.ac.il, Yehudayoff, Amir; Weizmann Institute; Amir.yehudayoff@weizmann.ac.il
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
Random Graph-Homomorphisms and Logarithmic Degree (2007)
Benjamini, Itai; Weizmann Institute; Itai.benjamini@weizmann.ac.il, Yadin, Ariel; Weizmann Institute; Ariel.yadin@weizmann.ac.il, Yehudayoff, Amir; Weizmann Institute; Amir.yehudayoff@weizmann.ac.il
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
Long Range Percolation Mixing Time (2007)
Benjamini, Itai, Berger, Noam, Yadin, Ariel
We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotically almost sure mixing time of the graph created by long-range percolation on the cycle of length N (Z/NZ). While it is...
Diffusion Limited Aggregation on a Cylinder (2007)
We consider the DLA process on a cylinder G x N. It is shown that this process "grows arms", provided that the base graph G has small enough mixing time. Specifically, if the mixing time of G is at...
Maximal Arithmetic Progressions in Random Subsets (2007)
Itai Benjamini, Ariel Yadin, Ofer Zeitouni
Let U (N) denote the maximal length of arithmetic progressions in a random uni-form subset of {0,1} N. By an application of the Chen-Stein method, we show that U (N) −2log N / log 2 converges in...
Random Graph-Homomorphisms and Logarithmic Degree (2006)
Benjamini, Itai, Yadin, Ariel, Yehudayoff, Amir
A graph homomorphism between two graphs is a map from the vertex set of one graph to the vertex set of the other graph, that maps edges to edges. In this note we study the range of a uniformly chosen...
Rate of Escape of the Mixer Chain (2005)
The mixer chain on a graph G is the following Markov chain. Place tiles on the vertices of G, each tile labeled by its corresponding vertex. A "mixer" moves randomly on the graph, at each step either...