Cover Image

Stochastic Matching via Local Sparsification

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ahmadian, Sara, Cohen, Edith, Roghani, Mohammad
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Cost of Compression: Tight Quadratic Black-Box Attacks on Sketches for $\ell_2$ Norm Estimation
by: Ahmadian, Sara, et al.
Published: (2025)

Unmasking Vulnerabilities: Cardinality Sketches under Adaptive Inputs
by: Ahmadian, Sara, et al.
Published: (2024)

Generalized Top-k Mallows Model for Ranked Choices
by: Haddadan, Shahrzad, et al.
Published: (2025)

Structure-Aware Spectral Sparsification via Uniform Edge Sampling
by: He, Kaiwen, et al.
Published: (2025)

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

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

Online Sparsification of Bipartite-Like Clusters in Graphs
by: Das, Joyentanuj, et al.
Published: (2025)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

Tight Bounds for Answering Adaptively Chosen Concentrated Queries
by: Rapoport, Emma, et al.
Published: (2025)

Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
by: Jin, Yujia, et al.
Published: (2024)

GIST: Greedy Independent Set Thresholding for Max-Min Diversification with Submodular Utility
by: Fahrbach, Matthew, et al.
Published: (2024)

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

Importance Sparsification for Sinkhorn Algorithm
by: Li, Mengyu, et al.
Published: (2023)

Unlearning Offline Stochastic Multi-Armed Bandits
by: Ye, Zichun, et al.
Published: (2026)

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

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Sublinear Metric Steiner Tree via Improved Bounds for Set Cover
by: Mahabadi, Sepideh, et al.
Published: (2024)

MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation
by: Hayderi, Alexandre, et al.
Published: (2024)

Hierarchical Clustering via Local Search
by: Jowhari, Hossein
Published: (2024)

A Simple Analysis of Ranking in General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Improved Approximation for Ranking on General Graphs
by: Derakhshan, Mahsa, et al.
Published: (2025)

Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams
by: Bakshi, Ainesh, et al.
Published: (2023)

inGRASS: Incremental Graph Spectral Sparsification via Low-Resistance-Diameter Decomposition
by: Aghdaei, Ali, et al.
Published: (2024)

Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph
by: Kamath, Gautam, et al.
Published: (2025)

Finite Sample Bounds for Learning with Score Matching
by: Smedira, Devin, et al.
Published: (2026)

Parsimonious Learning-Augmented Online Metric Matching
by: Shin, Yongho, et al.
Published: (2026)

Sharper Bounds for Chebyshev Moment Matching, with Applications
by: Musco, Cameron, et al.
Published: (2024)

Fast and Efficient Matching Algorithm with Deadline Instances
by: Song, Zhao, et al.
Published: (2023)

Stochastic Matching via In-n-Out Local Computation Algorithms
by: Azarmehr, Amir, et al.
Published: (2024)

Sublinear Time Algorithm for Online Weighted Bipartite Matching
by: Hu, Hang, et al.
Published: (2022)

Stochastic Bandits with ReLU Neural Networks
by: Xu, Kan, et al.
Published: (2024)

Semi-Bandit Learning for Monotone Stochastic Optimization
by: Agarwal, Arpit, et al.
Published: (2023)

Stable Matching with Interviews
by: Ashlagi, Itai, et al.
Published: (2025)

Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond
by: Axiotis, Kyriakos, et al.
Published: (2024)

Stochastic Submodular Bandits with Delayed Composite Anonymous Bandit Feedback
by: Pedramfar, Mohammad, et al.
Published: (2023)

Functional Stochastic Localization
by: Gu, Anming, et al.
Published: (2026)

Perspectives on Stochastic Localization
by: Shi, Bobby, et al.
Published: (2025)

Learning on the Edge: Online Learning with Stochastic Feedback Graphs
by: Esposito, Emmanuel, et al.
Published: (2022)

Stochastic $k$-Submodular Bandits with Full Bandit Feedback
by: Nie, Guanyu, et al.
Published: (2024)

Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
by: Burathep, Kunanon, et al.
Published: (2025)