Cover Image

Stochastic Matching via In-n-Out Local Computation Algorithms

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Azarmehr, Amir, Behnezhad, Soheil, Ghafari, Alma, Rubinfeld, Ronitt
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lower Bounds for Non-adaptive Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2025)

Markov Chains with Rewinding
by: Azarmehr, Amir, et al.
Published: (2026)

Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
by: Behnezhad, Soheil, et al.
Published: (2024)

Bipartite Matching in Massive Graphs: A Tight Analysis of EDCS
by: Azarmehr, Amir, et al.
Published: (2024)

Single-Pass Streaming CSPs via Two-Tier Sampling
by: Azarmehr, Amir, et al.
Published: (2026)

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance
by: Azarmehr, Amir, et al.
Published: (2025)

Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
by: Mitrović, Slobodan, et al.
Published: (2026)

Half-Approximating Maximum Dicut in the Streaming Setting
by: Azarmehr, Amir, et al.
Published: (2025)

Correlation Clustering Beyond the Pivot Algorithm
by: Behnezhad, Soheil, et al.
Published: (2024)

Locally computing edge orientations
by: Mitrović, Slobodan, et al.
Published: (2025)

Massively Parallel Minimum Spanning Tree in General Metric Spaces
by: Azarmehr, Amir, et al.
Published: (2024)

Beyond Worst Case Local Computation Algorithms
by: Biswas, Amartya Shankha, et al.
Published: (2024)

Testable algorithms for approximately counting edges and triangles in sublinear time and space
by: Eden, Talya, et al.
Published: (2025)

Optimal Algorithms for Augmented Testing of Discrete Distributions
by: Aliakbarpour, Maryam, et al.
Published: (2024)

Approximating Maximum Matching Requires Almost Quadratic Time
by: Behnezhad, Soheil, et al.
Published: (2024)

Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
by: Eden, Talya, et al.
Published: (2025)

No Price Tags? No Problem: Query Strategies for Unpriced Information
by: Nadimpalli, Shivam, et al.
Published: (2025)

Sublinear Algorithms for TSP via Path Covers
by: Behnezhad, Soheil, et al.
Published: (2023)

Quality control in sublinear time: a case study via random graphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries
by: Behnezhad, Soheil, et al.
Published: (2024)

Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
by: Aliakbarpour, Maryam, et al.
Published: (2025)

A Fast Coloring Oracle for Average Case Hypergraphs
by: Marcussen, Cassandra, et al.
Published: (2025)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Caterpillar of Thoughts: The Optimal Test-Time Algorithm for Large Language Models
by: Azarmehr, Amir, et al.
Published: (2026)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

Stochastic Matching via Local Sparsification
by: Ahmadian, Sara, et al.
Published: (2026)

Perfect Simulation of Las Vegas Algorithms via Local Computation
by: Fu, Xinyu, et al.
Published: (2023)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
by: Mehlhorn, Kurt, et al.
Published: (2026)

Matching Algorithms in the Sparse Stochastic Block Model
by: Brandenberger, Anna, et al.
Published: (2024)

Local Computation Algorithms for (Minimum) Spanning Trees on Expander Graphs
by: Peng, Pan, et al.
Published: (2026)

Streaming Algorithms via Local Algorithms for Maximum Directed Cut
by: Saxena, Raghuvansh R., et al.
Published: (2024)

Local Computation Algorithms for Knapsack: impossibility results, and how to avoid them
by: Canonne, Clément L., et al.
Published: (2025)

Engineering Hypergraph $b$-Matching Algorithms
by: Großmann, Ernestine, et al.
Published: (2024)

Algorithms for Parameterized String Matching with Mismatches
by: Saha, Apurba, et al.
Published: (2024)

Pruned Pivot: Correlation Clustering Algorithm for Dynamic, Parallel, and Local Computation Models
by: Dalirrooyfard, Mina, et al.
Published: (2024)

Semi-Streaming Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2025)

Efficient Parallel Algorithms for Hypergraph Matching
by: Reinstädtler, Henrik, et al.
Published: (2026)

Dynamic Pattern Matching with Wildcards
by: Naeini, Arshia Ataee, et al.
Published: (2026)