Talk:Expander walk sampling

Statistics Low‑importance

	This article is within the scope of WikiProject Statistics, a collaborative effort to improve the coverage of statistics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.StatisticsWikipedia:WikiProject StatisticsTemplate:WikiProject StatisticsStatistics
Low	This article has been rated as Low-importance on the importance scale.

Mathematics Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Low	This article has been rated as Low-priority on the project's priority scale.

Bit complexity of sampling from expanders

Latest comment: 13 years ago1 comment1 person in discussion

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

This page was redesigned at the edge.

Bit complexity of sampling from expanders