Talk:Expander walk sampling

Latest comment: 11 years ago by Nargle25787 in topic Bit complexity of sampling from expanders


Bit complexity of sampling from expanders

edit

I'm not an expert, but shouldn't the number of bits used in sampling from an infinite family of constant-degree expanders be $\log{n} + O(k)$? I'm counting $\log{n}$ bits for the initial seed, plus a constant number for each step in the walk, so $O(k)$. Nargle25787 (talk) 01:35, 8 April 2013 (UTC)Reply