42 citations · 147 across the 42 of their papers we have counts for
Showing 2009Show all
2 papers · 1 filter
cs.CC2009★ 2 cited
Homogeneous formulas and symmetric polynomials
Pavel Hrubes, Amir Yehudayoff
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 lea…
math.PR2009★ 14 cited
Entropy of Random Walk Range
Itai Benjamini, Gady Kozma, Ariel Yadin +1
We study the entropy of the set traced by an -step random walk on . We show that for , the entropy is of order . For , the entropy is of order $n/\log^…