Generating uniform linear extensions using few random bits
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908410866302976 |
|---|---|
| author | Huber, Mark |
| author_facet | Huber, Mark |
| contents | A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(σ\) such that for all \(i < j\) in \(A\), it holds that \(\neg(σ(j) \preceq σ(i))\). Consider the problem of generating uniformly from the set of linear extensions of a partial order. The best method currently known uses \(O(n^3 \ln(n))\) operations and \(O(n^3 \ln(n)^2)\) iid fair random bits to generate such a permutation. This paper presents a method that generates a uniform linear extension using only \(2.75 n^3 \ln(n)\) operations and \( 1.83 n^3 \ln(n) \) iid fair bits on average. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_14725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Generating uniform linear extensions using few random bits Huber, Mark Computational Complexity Probability Computation 68W20 G.3 A \emph{linear extension} of a partial order \(\preceq\) over items \(A = \{ 1, 2, \ldots, n \}\) is a permutation \(σ\) such that for all \(i < j\) in \(A\), it holds that \(\neg(σ(j) \preceq σ(i))\). Consider the problem of generating uniformly from the set of linear extensions of a partial order. The best method currently known uses \(O(n^3 \ln(n))\) operations and \(O(n^3 \ln(n)^2)\) iid fair random bits to generate such a permutation. This paper presents a method that generates a uniform linear extension using only \(2.75 n^3 \ln(n)\) operations and \( 1.83 n^3 \ln(n) \) iid fair bits on average. |
| title | Generating uniform linear extensions using few random bits |
| topic | Computational Complexity Probability Computation 68W20 G.3 |
| url | https://arxiv.org/abs/2506.14725 |