Cover Image

Generating uniform linear extensions using few random bits

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Huber, Mark
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Probability Computation 68W20 G.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On Identifying Critical Network Edges via Analyzing Changes in Shapes (Curvatures)
by: DasGupta, Bhaskar, et al.
Published: (2026)

Convergence in total variation for the kinetic Langevin algorithm
by: Lehec, Joseph
Published: (2024)

A new look at perfect simulation for chains with infinite memory
by: De Santis, Emilio, et al.
Published: (2025)

An Improved Drift Theorem for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

Beyond Worst-Case Analysis for Symbolic Computation: Root Isolation Algorithms
by: Ergür, Alperen A., et al.
Published: (2025)

Oblivious subspace embeddings for compressed Tucker decompositions
by: Pietrosanu, Matthew, et al.
Published: (2024)

Runtime Analyses of NSGA-III on Many-Objective Problems: Provable Exponential Speedup via Stochastic Population Update
by: Opris, Andre
Published: (2025)

Tight Runtime Guarantees From Understanding the Population Dynamics of the GSEMO Multi-Objective Evolutionary Algorithm
by: Doerr, Benjamin, et al.
Published: (2025)

Undercomplete Decomposition of Symmetric Tensors in Linear Time, and Smoothed Analysis of the Condition Number
by: Koiran, Pascal, et al.
Published: (2024)

A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
by: Opris, Andre
Published: (2025)

Runtime Analyses of NSGA-III on Many-Objective Problems
by: Opris, Andre, et al.
Published: (2024)

Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
by: Opris, Andre, et al.
Published: (2024)

The Distributional Tail of Worst-Case Quickselect
by: Płecha, Witold
Published: (2026)

Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity
by: Chen, Zongchen, et al.
Published: (2022)

The Power of Filling in Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2022)

Mean-Biased Processes for Balanced Allocations
by: Los, Dimitrios, et al.
Published: (2023)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
by: Chiclana, Rafael, et al.
Published: (2025)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
by: Amireddy, Prashanth, et al.
Published: (2025)

Generating DDPM-based Samples from Tilted Distributions
by: Mandal, Himadri, et al.
Published: (2026)

Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
by: Bhandari, Kritika, et al.
Published: (2025)

Many Objective Problems Where Crossover is Provably Essential
by: Opris, Andre
Published: (2024)

The degree-restricted random process is far from uniform
by: Molloy, Michael, et al.
Published: (2022)

Algorithms for Generating Small Random Samples
by: Cicirello, Vincent A.
Published: (2024)

Racing to Idle: Energy Efficiency of Matrix Multiplication on Heterogeneous CPU and GPU Architectures
by: Ansari, Mufakir Qamar, et al.
Published: (2025)

A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
by: Feng, Weiming, et al.
Published: (2022)

Naively Sorting Evolving Data is Optimal and Robust
by: Giakkoupis, George, et al.
Published: (2024)

On the difficulty of order constrained pattern matching with applications to feature matching based malware detection
by: Liyanage, Adiesha, et al.
Published: (2025)

Complexity and algorithms for Swap median and relation to other consensus problems
by: Cunha, Luís, et al.
Published: (2024)

On sampling diluted Spin-Glasses with unbounded interactions
by: Efthymiou, Charilaos, et al.
Published: (2026)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

Towards a Rigorous Understanding of the Population Dynamics of the NSGA-III: Tight Runtime Bounds
by: Opris, Andre
Published: (2025)

Random-Order Online Independent Set of Intervals and Hyperrectangles
by: Garg, Mohit, et al.
Published: (2024)

How to Compute a Moving Sum
by: Maslen, David K., et al.
Published: (2025)

Population Protocols Revisited: Parity and Beyond
by: Gąsieniec, Leszek, et al.
Published: (2025)

Derandomization with Pseudorandomness
by: Karayel, Emin
Published: (2024)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Spectrum Estimation through Kirchhoff Random Forests
by: Barthelmé, Simon, et al.
Published: (2025)

CUBO: Self-Contained Retrieval-Augmented Generation on Consumer Laptops 10 GB Corpora, 16 GB RAM, Single-Device Deployment
by: Astrino, Paolo
Published: (2026)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
by: Zhong, Xianghui
Published: (2018)

Computing moment polytopes -- with a focus on tensors, entanglement and matrix multiplication
by: Berg, Maxim van den, et al.
Published: (2025)