Homogeneous formulas and symmetric polynomials (2009)
Hrubes, Pavel, Yehudayoff, Amir
We investigate the arithmetic formula complexity of the elementary symmetric polynomials S(k,n). We show that every multilinear homogeneous formula computing S(k,n) has size at least k^(Omega(log...
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...
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits (2009)
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there...
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...
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits (2008)
Zeev Dvir, Amir Shpilka, Amir Yehudayoff
In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there...
Lower Bounds and Separations for Constant Depth Multilinear Circuits (2008)
We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the...
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...
Pseudorandomness for Width 2 Branching Programs (2008)
Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff
Recently Bogdanov and Viola (FOCS 2007) and Lovett (ECCC-07) constructed pseudorandom generators that fool degree k polynomials over F2 for an arbitrary constant k. We show that such generators can...
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...
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...
t-Wise Independence with Local Dependencies (2007)
Gradwohl, Ronen, Yehudayoff, Amir
In this note we prove a large deviation bound on the sum of random variables with the following dependency structure: there is a dependency graph $G$ with a bounded chromatic number, in which each...
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits (2007)
Ran Raz, Amir Shpilka, Amir Yehudayoff
We construct an explicit polynomial f(x1,...,xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n 4/3 / log 2 n). The...
Balancing Syntactically Multilinear Arithmetic Circuits (2007)
In their seminal paper, Valiant, Skyum, Berkowitz and Rackoff proved that arithmetic circuits can be balanced [VSBR]. That is, [VSBR] showed that for every arithmetic circuit Φ of size s and degree...
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits (2007)
Ran Raz, Amir Shpilka, Amir Yehudayoff
We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n 4/3 / log 2 n)....
Balancing Syntactically Multilinear Arithmetic Circuits (2007)
In their seminal paper, Valiant, Skyum, Berkowitz and Rackoff proved that arithmetic circuits can be balanced [VSBR]. That is, [VSBR] showed that for every arithmetic circuit Φ of size s and degree...
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors (2007)
We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for...
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors (2007)
We study a new method for proving lower bounds for subclasses of arithmetic circuits. Roughly speaking, the lower bound is proved by bounding the correlation between the coefficients ’ vector of a...
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits (2007)
Ran Raz, Amir Shpilka, Amir Yehudayoff
We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n 4/3 / log 2 n)....
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...