pith. sign in

arxiv: 2605.29566 · v1 · pith:C7PHIXJUnew · submitted 2026-05-28 · 💻 cs.DS · math.PR

Sampling Directed Eulerian Tours in widetilde O(m^(3/2)) Time

Nima Anari This is my paper

Pith reviewed 2026-06-29 00:33 UTC · model grok-4.3

classification 💻 cs.DS math.PR
keywords directed eulerian toursmarkov chain samplingmixing time analysisgraph algorithmsdata structureseulerian circuitsrandomized algorithms
0
0 comments X

The pith

A randomized algorithm samples nearly uniform directed Eulerian tours in tilde O(m^{3/2}) time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a randomized algorithm to sample a nearly uniform Eulerian tour from any directed Eulerian multigraph on m arcs. It targets the worst-case setting and improves on prior mn-style time bounds that arise from arborescence sampling, especially when the graph is sparse. The approach reduces the problem to the special case of 2-in/2-out graphs by introducing a local Markov chain called the flip-repair walk. This chain is shown to mix in nearly linear steps and is realized efficiently with a dynamic chord data structure. A degree-reduction wrapper then lifts the core sampler to graphs of arbitrary degree while keeping the overall running time at tilde O(m^{3/2}).

Core claim

We give a randomized algorithm that samples a nearly uniform Eulerian tour of a directed Eulerian multigraph with m arcs in tilde O(m^{3/2}) time. The guarantee is worst-case and applies to arbitrary directed Eulerian multigraphs. The core case is a 2-in/2-out graph. We introduce a new local Markov chain, the flip-repair walk: one step locally splits a tour into two circuits and then chooses uniformly among the local flips that repair the state to one tour. We prove that this walk mixes in nearly linear many steps and implement the walk using a dynamic chord data structure. A pointwise degree-reduction wrapper extends the sampler from this degree-two core to arbitrary degrees while preservin

What carries the argument

The flip-repair walk, a local Markov chain on 2-in/2-out directed graphs that splits a tour into two circuits and repairs it by uniform choice among local flips.

If this is right

  • The sampler works for arbitrary directed Eulerian multigraphs under worst-case guarantees.
  • It breaks the mn-type arborescence-sampling barrier on sparse graphs.
  • The flip-repair walk mixes in nearly linear steps.
  • The implementation relies on a dynamic chord data structure to perform each step efficiently.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-repair idea might yield fast samplers for other circuit-based objects such as undirected Eulerian tours or cycle covers.
  • The mixing analysis could be reused as a template for designing polynomial-time samplers in related combinatorial settings where global moves are expensive.
  • Further refinement of the dynamic data structure might push the exponent below 3/2 without changing the high-level plan.

Load-bearing premise

The flip-repair walk on 2-in/2-out graphs mixes in nearly linear steps.

What would settle it

A concrete 2-in/2-out directed multigraph on which the flip-repair walk requires superlinear mixing time would falsify the central mixing claim and therefore the overall time bound.

Figures

Figures reproduced from arXiv: 2605.29566 by Nima Anari.

Figure 1
Figure 1. Figure 1: The sampler reduces to the degree-two flip–repair walk and then projects back to [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: One step of the skew-determinantal flip–repair walk. From an even feasible set [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: In a 2-in/2-out graph, the first flip cuts the current tour at the two occurrences of 𝑥. Apart from flipping 𝑥 back, a repair flip restores one tour exactly when its chord crosses 𝑥; the four intervals are reassembled without reversing orientation. Lemma 19 (Crossing criterion). Let 𝑥 be the first flipped vertex. Its two occurrences split the tour circle into two open intervals 𝐼 and 𝐼 𝑐 . After flipping 𝑥… view at source ↗
Figure 4
Figure 4. Figure 4: A crossing query in the chunk data structure. Boundary chunks are inspected explicitly. [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A degree-𝑑 vertex is replaced by a 𝑑-wire sparse switching network. A short guard layer touches every wire, and a random construction chooses the remaining pairs of wires that meet at switches. Uniform switch settings then induce a pointwise almost-uniform permutation of the 𝑑 local successors. directed path whose internal points are ports and whose endpoints are switches is replaced by one arc. The guard … view at source ↗
Figure 6
Figure 6. Figure 6: Parity stochastic covering. After removing the conditioned coordinate [PITH_FULL_IMAGE:figures/full_fig_p035_6.png] view at source ↗
read the original abstract

We give a randomized algorithm that samples a nearly uniform Eulerian tour of a directed Eulerian multigraph with $m$ arcs in $\widetilde O(m^{3/2})$ time. The guarantee is worst-case, applies to arbitrary directed Eulerian multigraphs, and breaks the $mn$-type arborescence-sampling barrier on sparse graphs. The core case is a $2$-in/$2$-out graph. We introduce a new local Markov chain, the flip--repair walk: one step locally splits a tour into two circuits and then chooses uniformly among the local flips that repair the state to one tour. We prove that this walk mixes in nearly linear many steps and implement the walk using a dynamic chord data structure. A pointwise degree-reduction wrapper extends the sampler from this degree-two core to arbitrary degrees while preserving the $\widetilde O(m^{3/2})$ total running time. The high-level algorithmic plan, the switching-network reduction, and the dynamic data-structure argument were devised by the author. The author conjectured the mixing theorem underlying the analysis, and GPT 5.5 Pro Extended produced its linear-algebra proof. Codex assisted with manuscript assembly and typesetting.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The manuscript claims a randomized algorithm that samples a nearly uniform Eulerian tour of a directed Eulerian multigraph with m arcs in ilde O(m^{3/2}) time. The guarantee is worst-case and applies to arbitrary directed Eulerian multigraphs. The core case reduces to 2-in/2-out graphs via a new local Markov chain (the flip-repair walk) that is claimed to mix in nearly linear steps; the walk is implemented with a dynamic chord data structure, and a pointwise degree-reduction wrapper extends the result to general degrees while preserving the runtime bound. The high-level plan, switching-network reduction, and data-structure argument are by the author; the mixing theorem was conjectured by the author and its linear-algebraic proof produced by GPT.

Significance. If the mixing-time bound holds, the result would be a notable improvement over prior mn-type arborescence-sampling barriers, especially on sparse graphs. The flip-repair chain and dynamic chord structure constitute genuine algorithmic contributions. The paper also ships an explicit linear-algebraic mixing proof (albeit AI-generated), which is a positive for verifiability if the derivation is correct.

major comments (1)
  1. [Abstract / mixing analysis] The nearly-linear mixing claim for the flip-repair walk on 2-in/2-out graphs is the single load-bearing analytic step that converts the local chain into the stated ilde O(m^{3/2}) runtime (see abstract and the reduction paragraph). The linear-algebraic analysis of the transition matrix (conjectured by the author, produced by GPT) must be independently verified with explicit spectral-gap bounds and error terms; without this verification the runtime guarantee collapses.
minor comments (1)
  1. [Introduction] The disclosure that GPT produced the mixing proof should be expanded in the introduction or acknowledgments to clarify the exact scope of AI assistance versus author verification.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the central role of the mixing analysis. We address the major comment below and commit to revisions that directly resolve the verification concern.

read point-by-point responses

  1. Referee: [Abstract / mixing analysis] The nearly-linear mixing claim for the flip-repair walk on 2-in/2-out graphs is the single load-bearing analytic step that converts the local chain into the stated ṯilde O(m^{3/2}) runtime (see abstract and the reduction paragraph). The linear-algebraic analysis of the transition matrix (conjectured by the author, produced by GPT) must be independently verified with explicit spectral-gap bounds and error terms; without this verification the runtime guarantee collapses.

    Authors: We agree that the mixing-time bound is the load-bearing analytic step and that the linear-algebraic derivation requires explicit, independently verifiable spectral-gap bounds and error terms. The authors have now manually re-derived and verified the argument, confirming the claimed gap and all error terms. In the revised manuscript we will replace the current presentation with a fully expanded, self-contained linear-algebraic section that states the transition matrix, derives the gap explicitly, and tracks all error terms with concrete constants. A short appendix will document the verification steps. These changes will make the runtime guarantee fully rigorous without altering any algorithmic claims. revision: yes

Circularity Check

0 steps flagged

No circularity; mixing-time proof is internal and independent of runtime claim

full rationale

The paper states that it proves the flip-repair walk mixes in nearly linear steps via linear-algebraic analysis of the transition matrix, and this bound is used to obtain the overall ilde O(m^{3/2}) runtime after degree reduction and data-structure implementation. No equation or parameter in the provided text reduces the runtime bound to a fitted input, self-definition, or prior self-citation; the mixing theorem is presented as a proved result within the manuscript rather than imported from an earlier paper by the same author. All other components (chord data structure, switching-network reduction) are polynomial-time once the mixing bound is granted, but the bound itself does not collapse to the runtime claim by construction. The note that the author conjectured the theorem and GPT produced the proof does not create circularity, as the proof is supplied in the current work and is not a load-bearing citation to unverified prior output.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper introduces one new algorithmic object (the flip-repair walk) whose mixing time is the key unverified analytic step. No free parameters or invented physical entities appear in the abstract.

axioms (1)
  • standard math Standard Markov-chain mixing-time analysis via linear algebra on the transition matrix suffices to bound the number of steps.
    The abstract states that the mixing theorem was proved by linear-algebra methods.
invented entities (1)
  • flip-repair walk no independent evidence
    purpose: Local Markov chain that splits and repairs Eulerian tours
    Newly defined in the paper for this sampling task.

pith-pipeline@v0.9.1-grok · 5739 in / 1299 out tokens · 32324 ms · 2026-06-29T00:33:17.932715+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

5 extracted references · 5 canonical work pages · 2 internal anchors

  1. [1]

    Breaking the quadratic barrier for matroid intersection , booktitle =

    [Ali+21] Yeganeh Alimohammadi, Nima Anari, Kirankumar Shiragur, and Thuy-Duong Vuong. “Fractionally Log-Concave and Sector-Stable Polynomials: Counting Planar Matchings and More”. In:Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2021, pp. 433–446.doi:10.1145/ 3406325.3451123. arXiv:2102.02...

    work page doi:10.1145/3406325.3451091 2021

  2. [2]

    Monte Carlo Markov Chain Algorithms for Sampling Strongly Rayleigh Distributions and Determinantal Point Processes

    ProceedingsofMachineLearningResearch.PMLR,2016,pp.103–115.arXiv: 1602.05242 [cs.DS]. [BA51] N. G. de Bruijn and T. van Aardenne-Ehrenfest. “Circuits and Trees in Oriented Linear Graphs”. In:Simon Stevin28 (1951), pp. 203–217. [BBL09] Julius Borcea, Petter Brändén, and Thomas M. Liggett. “Negative Dependence and the Geometry of Polynomials”. In:Journal of t...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1090/s0894-0347-08-00618-8 2016

  3. [3]

    Lagrangian representation for fermionic linear optics

    [Bou87] André Bouchet. “Unimodularity and Circle Graphs”. In:Discrete Mathematics66.1–2 (1987), pp. 203–208.doi:10.1016/0012-365X(87)90132-4. [Bou92] André Bouchet. “A Characterization of Unimodular Orientations of Simple Graphs”. In:Journal of Combinatorial Theory, Series B56.1 (1992), pp. 45–54.doi:10.1016/0095- 8956(92)90005-I. 40 [BPS18] Lucas Boczkow...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/0012-365x(87)90132-4 1987

  4. [4]

    Spectral Independence via Stability and Applications to Holant-Type Problems

    [CLV21] Zongchen Chen, Kuikui Liu, and Eric Vigoda. “Spectral Independence via Stability and Applications to Holant-Type Problems”. In:Proceedings of the 62nd Annual IEEE Sym- posium on Foundations of Computer Science. 2021, pp. 149–160.doi:10.1109/FOCS52979. 2021.00023. arXiv:2106.03366 [cs.DS]. [Czu15] Artur Czumaj. “Random Permutations Using Switching ...

    work page doi:10.1109/focs52979 2021

  5. [5]

    A Permutation Network

    Lecture Notes in Computer Science. Springer, 1997, pp. 57–66.doi:10.1007/3-540-63248-4_6. [Wak68] Abraham Waksman. “A Permutation Network”. In:Journal of the ACM15.1 (1968), pp. 159–163.doi:10.1145/321439.321449. 42

    work page doi:10.1007/3-540-63248-4_6 1997