Cover Image

A Combinatorial Characterization of Constant Mixing Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lau, Lap Chi, Liu, Raymond
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Sparsification by Deterministic Discrepancy Walk
by: Lau, Lap Chi, et al.
Published: (2024)

On the Houdré-Tetali conjecture about an isoperimetric constant of graphs
by: Lau, Lap Chi, et al.
Published: (2024)

A Simple and Combinatorial Approach to Proving Chernoff Bounds and Their Generalizations
by: Kuszmaul, William
Published: (2025)

A Strongly Subcubic Combinatorial Algorithm for Triangle Detection with Applications
by: Dumitrescu, Adrian
Published: (2024)

Switching Classes: Characterization and Computation
by: Antony, Dhanyamol, et al.
Published: (2024)

A Freeable Matrix Characterization of Bipartite Graphs of Ferrers Dimension Three
by: Chalermsook, Parinya, et al.
Published: (2025)

Combinatorial optimization of the coefficient of determination
by: Harary, Marc
Published: (2024)

Characterization of Circular-arc Graphs: II. McConnell Flipping
by: Cao, Yixin, et al.
Published: (2024)

Optimal Algorithm for Paired-Domination in Distance-Hereditary Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

Fast Mixing in Sparse Random Ising Models
by: Liu, Kuikui, et al.
Published: (2024)

Mixing on Generalized Associahedra
by: Chang, William, et al.
Published: (2024)

A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
by: Dhawan, Abhishek
Published: (2024)

A Linear-Time Algorithm for Finding an Odd Cycle Through Two Specified Vertices
by: Kano, Takumi, et al.
Published: (2026)

Bounding Width on Graph Classes of Constant Diameter
by: Dabrowski, Konrad K., et al.
Published: (2025)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
by: Bell, Tolson, et al.
Published: (2023)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
by: Korhonen, Tuukka
Published: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

Streaming and Communication Complexity of Load-Balancing via Matching Contractors
by: Assadi, Sepehr, et al.
Published: (2024)

Lattice Structure and Efficient Basis Construction for Strongly Connected Orientations
by: Liu, Siyue, et al.
Published: (2026)

Complexity and Algorithm for the Matching vertex-cutset Problem
by: Li, Hengzhe, et al.
Published: (2025)

Experimental Design Using Interlacing Polynomials
by: Lau, Lap Chi, et al.
Published: (2024)

A Note on Generic Tangle Algorithms
by: Elbracht, Christian, et al.
Published: (2020)

A note on Ordered Ruzsa-Szemerédi graphs
by: Pratt, Kevin
Published: (2025)

A Lower Bound for the Max Entropy Algorithm for TSP
by: Jin, Billy, et al.
Published: (2023)

A Faster Deterministic Approximation Algorithm for TTP-2
by: Kanaya, Yuga, et al.
Published: (2023)

A Maximum Linear Arrangement Problem on Directed Graphs
by: DeVos, Matt, et al.
Published: (2018)

A Unified View of Graph Regularity via Matrix Decompositions
by: Bodwin, Greg, et al.
Published: (2019)

A faster algorithm for Vertex Cover parameterized by solution size
by: Harris, David G., et al.
Published: (2022)

A refined graph container lemma and applications to the hard-core model on bipartite expanders
by: Jenssen, Matthew, et al.
Published: (2024)

A LP-rounding based algorithm for soft capacitated facility location problem with submodular penalties
by: Xiao, Hanyin, et al.
Published: (2025)

A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order
by: Glover, Charles N.
Published: (2024)

Characterizing and Testing Principal Minor Equivalence of Matrices
by: Chatterjee, Abhranil, et al.
Published: (2024)

An Improved Upper Bound for the Euclidean TSP Constant Using Band Crossovers
by: Gaudio, Julia, et al.
Published: (2026)

Testing H-freeness on sparse graphs, the case of bounded expansion
by: Humeau, Samuel, et al.
Published: (2025)

Generating the Spanning Trees of Series-Parallel Graphs up to Graph Automorphism
by: Karamchedu, Mithra, et al.
Published: (2025)

Liar's vertex-edge domination in unit disk graph
by: Bhattacharya, Debojyoti, et al.
Published: (2025)

Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
by: Jones, Mark, et al.
Published: (2025)

Perfect Fractional Matchings in Bipartite Graphs Via Proportional Allocations
by: Hathcock, Daniel, et al.
Published: (2025)

Face-hitting dominating sets in planar graphs: Alternative proof and linear-time algorithm
by: Biedl, Therese
Published: (2025)

Sub-$n^k$ Deterministic algorithm for minimum $k$-way cut in simple graphs
by: Daga, Mohit
Published: (2025)