Approximating Random Walks in $\widetilde{O}(\log n + \log^2 κ)$ Space for $κ$-Conditioned Graphs
For $κ>1$, a directed graph is $κ$-conditioned if it is $κ$-mixing and its stationary distribution is approximated by the uniform distribution within a factor of $κ$. We present a deterministic algorithm that approximates the stationary distribution of a $κ$-conditioned graph to inverse polynomial r...
שמור ב:
| מחבר ראשי: | |
|---|---|
| פורמט: | Artículo |
| יצא לאור: |
2026
|
| נושאים: | |
| גישה מקוונת: | https://arxiv.org/abs/2610.06796 http://arxiv.org/abs/2610.06796 |
| תגים: |
אין תגיות, היה/י הראשונ/ה לתייג את הרשומה!
|
היה/י הראשונ/ה לכתוב הערה!