Buchumschlag

Markov Chains with Rewinding

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Azarmehr, Amir, Behnezhad, Soheil, Ghafari, Alma, Sudan, Madhu
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Lower Bounds for Non-adaptive Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Stochastic Matching via In-n-Out Local Computation Algorithms
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
von: Azarmehr, Amir, et al.
Veröffentlicht: (2026)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Half-Approximating Maximum Dicut in the Streaming Setting
von: Azarmehr, Amir, et al.
Veröffentlicht: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
von: Azarmehr, Amir, et al.
Veröffentlicht: (2024)

Correlation Clustering Beyond the Pivot Algorithm
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Quality control in sublinear time: a case study via random graphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

On Algorithmic Robustness of Corrupted Markov Chains
von: Gaitonde, Jason, et al.
Veröffentlicht: (2025)

Markov Chains Approximate Message Passing
von: Rajaraman, Amit, et al.
Veröffentlicht: (2025)

Finding the root in random nearest neighbor trees
von: Brandenberger, Anna, et al.
Veröffentlicht: (2024)

Locally Stationary Distributions: A Framework for Analyzing Slow-Mixing Markov Chains
von: Liu, Kuikui, et al.
Veröffentlicht: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2024)

Errors are Robustly Tamed in Cumulative Knowledge Processes
von: Brandenberger, Anna, et al.
Veröffentlicht: (2023)

Phase Transitions via Complex Extensions of Markov Chains
von: Liu, Jingcheng, et al.
Veröffentlicht: (2024)

Sublinear Algorithms for TSP via Path Covers
von: Behnezhad, Soheil, et al.
Veröffentlicht: (2023)

A Theory of Spectral CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Near-optimal Hypergraph Sparsification in Insertion-only and Bounded-deletion Streams
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Efficient Algorithms and New Characterizations for CSP Sparsification
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Almost-Tight Bounds on Preserving Cuts in Classes of Submodular Hypergraphs
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Near-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
von: Saxena, Raghuvansh R., et al.
Veröffentlicht: (2024)

Faster Mixing of the Jerrum-Sinclair Chain
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2025)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

Discrete Optimal Transport: Rapid Convergence of Simulated Annealing Algorithms
von: He, Yuchen, et al.
Veröffentlicht: (2026)

Sampling Sphere Packings with Continuum Glauber Dynamics
von: Kuchukova, Aiya, et al.
Veröffentlicht: (2026)

Subquadratic Counting via Perfect Marginal Sampling
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2026)

Power laws and power-of-two-choices
von: Redlich, Amanda
Veröffentlicht: (2026)

Intermittent Cauchy walks enable optimal 3D search across target shapes and sizes
von: Stromieri, Matteo, et al.
Veröffentlicht: (2026)

Near-Optimal Parallel Approximate Counting via Sampling
von: Harris, David G., et al.
Veröffentlicht: (2026)

Edge-Tilting Field Dynamics: Rapid Mixing at the Uniqueness Threshold and Optimal Mixing for Swendsen-Wang Dynamics
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2026)

Threshold Rules for the Classical Prophet Inequality
von: Zhang, Jiechen
Veröffentlicht: (2026)

Distance Estimation for High-Dimensional Discrete Distributions
von: Kumar, Gunjan, et al.
Veröffentlicht: (2023)

Mixing of general biased adjacent transposition chains
von: Gheissari, Reza, et al.
Veröffentlicht: (2025)

Robust recovery for stochastic block models, simplified and generalized
von: Mohanty, Sidhanth, et al.
Veröffentlicht: (2024)