\begin{thebibliography}{10}

\bibitem{knuth}
Donald E. Knuth.
\emph{The Art of Computer Programming, Volume 3: Sorting and Searching.}
Second edition, Addison-Wesley, 1998.
\href{https://www.informit.com/store/art-of-computer-programming-volume-3-sorting-and-searching-9780201896855}{Publisher's page}.

\bibitem{fredman}
Michael L. Fredman.
\emph{How good is the information theory bound in sorting?}
Theoretical Computer Science 1(4), 355--361, 1976.
\href{https://doi.org/10.1016/0304-3975(76)90078-5}{doi:10.1016/0304-3975(76)90078-5}.

\bibitem{atallah}
Mikhail J. Atallah and S. Rao Kosaraju.
\emph{An adversary-based lower bound for sorting.}
Information Processing Letters 13(2), 55--57, 1981.

\bibitem{borodin}
Allan Borodin, Leonidas J. Guibas, Nancy A. Lynch, and Andrew C. Yao.
\emph{Efficient searching using partial ordering.}
Information Processing Letters 12(2), 71--75, 1981.
\href{https://doi.org/10.1016/0020-0190(81)90005-3}{doi:10.1016/0020-0190(81)90005-3}.

\bibitem{richards}
Dana Richards and Pravin M. Vaidya.
\emph{On the distribution of comparisons in sorting algorithms.}
BIT 28, 764--774, 1988.
\href{https://lic225.github.io/vaidya/sorting_BIT88.pdf}{Authors' paper}.

\bibitem{brodal}
Gerth St{\o}lting Brodal, Shiva Chaudhuri, and Jaikumar Radhakrishnan.
\emph{The randomized complexity of maintaining the minimum.}
Nordic Journal of Computing 3(4), 337--351, 1996.
\href{https://www.brics.dk/RS/96/40/BRICS-RS-96-40.pdf}{Authors' report, BRICS RS-96-40}.


\bibitem{kzz-min}
Haim Kaplan, Or Zamir, and Uri Zwick.
\emph{The amortized cost of finding the minimum.}
Proceedings of the Twenty-Sixth Annual ACM--SIAM Symposium on Discrete Algorithms
(SODA), 757--768, 2015. Published online 22 December 2014.
\href{https://doi.org/10.1137/1.9781611973730.51}{doi:10.1137/1.9781611973730.51}.
\href{https://zamir.prof/pub/FindMin_OrZamir.pdf}{Authors' paper}.

\bibitem{kzz}
Haim Kaplan, Or Zamir, and Uri Zwick.
\emph{A sort of an adversary.}
Proceedings of the Thirtieth Annual ACM--SIAM Symposium on Discrete Algorithms
(SODA), 1291--1310, 2019.
\href{https://doi.org/10.1137/1.9781611975482.79}{doi:10.1137/1.9781611975482.79}.

\bibitem{stanley}
Richard P. Stanley.
\emph{Two poset polytopes.}
Discrete \& Computational Geometry 1, 9--23, 1986.
\href{https://doi.org/10.1007/BF02187680}{doi:10.1007/BF02187680}.
\href{https://math.mit.edu/~rstan/pubs/pubfiles/66.pdf}{Author's copy}.

\bibitem{brightwell}
Graham Brightwell and Peter Winkler.
\emph{Counting linear extensions.}
Order 8(3), 225--242, 1991.
\href{https://doi.org/10.1007/BF00383444}{doi:10.1007/BF00383444}.

\bibitem{dfk}
Martin Dyer, Alan Frieze, and Ravi Kannan.
\emph{A random polynomial-time algorithm for approximating the volume of convex bodies.}
Journal of the ACM 38(1), 1--17, 1991.
\href{https://doi.org/10.1145/102782.102783}{doi:10.1145/102782.102783}.
\href{https://www.math.cmu.edu/~af1p/Texfiles/oldvolume.pdf}{Authors' manuscript}.

\bibitem{kahn-kim}
Jeff Kahn and Jeong Han Kim.
\emph{Entropy and sorting.}
Journal of Computer and System Sciences 51(3), 390--399, 1995.
\href{https://doi.org/10.1006/jcss.1995.1077}{doi:10.1006/jcss.1995.1077}.


\bibitem{prekopa}
Andr\'as Pr\'ekopa.
\emph{On logarithmic concave measures and functions.}
Acta Scientiarum Mathematicarum 34, 335--343, 1973.
\href{https://acta.bibl.u-szeged.hu/14411/1/math_034_335-343.pdf}{Publisher's paper}.

\bibitem{cardinal-production}
Jean Cardinal, Samuel Fiorini, Gwena\"el Joret, Rapha\"el M. Jungers,
and J. Ian Munro.
\emph{An efficient algorithm for partial order production.}
SIAM Journal on Computing 39(7), 2927--2940, 2010.
\href{https://doi.org/10.1137/090759860}{doi:10.1137/090759860}.
\href{https://arxiv.org/abs/0811.2572}{Authors' manuscript}.

\bibitem{imprecise-points}
Ivor van der Hoog, Irina Kostitsyna, Maarten L\"offler, and Bettina Speckmann.
\emph{Preprocessing ambiguous imprecise points.}
35th International Symposium on Computational Geometry (SoCG),
LIPIcs 129, 42:1--42:16, 2019.
\href{https://doi.org/10.4230/LIPIcs.SoCG.2019.42}{doi:10.4230/LIPIcs.SoCG.2019.42}.

\bibitem{interval-orders}
Ivor van der Hoog, Irina Kostitsyna, Maarten L\"offler, and Bettina Speckmann.
\emph{Sorting under partial (interval order) information.}
Journal of Computational Geometry 15(1), 143--171, 2024.
\href{https://doi.org/10.20382/jocg.v15i1a6}{doi:10.20382/jocg.v15i1a6}.


\bibitem{marked-order-polytopes}
Federico Ardila, Thomas Bliem, and Dido Salazar.
\emph{Gelfand--Tsetlin polytopes and Feigin--Fourier--Littelmann--Vinberg
polytopes as marked poset polytopes.}
Journal of Combinatorial Theory, Series A 118(8), 2454--2462, 2011.
\href{https://doi.org/10.1016/j.jcta.2011.06.004}{doi:10.1016/j.jcta.2011.06.004}.
\href{https://arxiv.org/abs/1008.2365}{arXiv:1008.2365}.

\bibitem{bencs-regts-volume}
Ferenc Bencs and Guus Regts.
\emph{Approximating the volume of a truncated relaxation of the independence polytope.}
Discrete \& Computational Geometry 76, 508--525, 2026.
\href{https://doi.org/10.1007/s00454-026-00824-y}{doi:10.1007/s00454-026-00824-y}.

\bibitem{chan-pak-survey}
Swee Hong Chan and Igor Pak.
\emph{Linear extensions of finite posets.}
EMS Surveys in Mathematical Sciences, published online 17 March 2025.
\href{https://doi.org/10.4171/EMSS/97}{doi:10.4171/EMSS/97}.
\href{https://www.math.ucla.edu/~pak/papers/LEsurvey11.pdf}{Authors' manuscript}.

\bibitem{talvitie-counting}
Topi Talvitie, Kustaa Kangas, Teppo Niinim\"aki, and Mikko Koivisto.
\emph{A scalable scheme for counting linear extensions.}
Proceedings of the Twenty-Seventh International Joint Conference on
Artificial Intelligence (IJCAI), 5119--5125, 2018.
\href{https://www.ijcai.org/proceedings/2018/710}{Publisher's page}.
\href{https://ijcai.org/proceedings/2018/0710.pdf}{Authors' paper}.

\bibitem{haeupler-sorting}
Bernhard Haeupler, Richard Hlad\'ik, John Iacono, V\'aclav Rozho\v{n},
Robert E. Tarjan, and Jakub T\v{e}tek.
\emph{Fast and simple sorting using partial information.}
Proceedings of the Thirty-Sixth Annual ACM--SIAM Symposium on Discrete
Algorithms (SODA), 2025.
\href{https://doi.org/10.1137/1.9781611978322.134}{doi:10.1137/1.9781611978322.134}.
\href{https://arxiv.org/abs/2404.04552}{Authors' manuscript}.

\bibitem{rutschmann-sorting}
Daniel Rutschmann.
\emph{Sorting under partial information with optimal preprocessing time
via unified bound heaps.}
Preprint, 2026. To appear at FOCS 2026.
\href{https://arxiv.org/abs/2604.12653}{arXiv:2604.12653}.

\bibitem{huber-sampling}
Mark Huber.
\emph{Near-linear time simulation of linear extensions of a height-2
poset with bounded interaction.}
Chicago Journal of Theoretical Computer Science 2014, Article 3, 1--16.
\href{https://doi.org/10.4086/cjtcs.2014.003}{doi:10.4086/cjtcs.2014.003}.

\bibitem{propp-wilson}
James G. Propp and David B. Wilson.
\emph{Exact sampling with coupled Markov chains and applications to
statistical mechanics.}
Random Structures \& Algorithms 9(1--2), 223--252, 1996.
\href{https://www.stat.berkeley.edu/~aldous/206-RWG/RWGpapers/propp_wilson.pdf}{Authors' paper}.

\end{thebibliography}