Jump to content

Talk:Expander walk sampling

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


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]