Cover Image

Tight Pair Query Lower Bounds for Matching and Earth Mover's Distance

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Azarmehr, Amir, Behnezhad, Soheil, Roghani, Mohammad, Rubinstein, Aviad
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

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

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

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

Data-Dependent LSH for the Earth Mover's Distance
by: Jayaram, Rajesh, et al.
Published: (2024)

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair
by: Beretta, Lorenzo, et al.
Published: (2025)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

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

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

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

Beyond matroids: Secretary Problem and Prophet Inequality with general constraints
by: Rubinstein, Aviad
Published: (2016)

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

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

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

Almost Tight Bounds for Online Hypergraph Matching
by: Tröbst, Thorben, et al.
Published: (2024)

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries
by: Shah, Vihan
Published: (2026)

A Tight Lower Bound for Cycle Detection in Grid Graphs
by: Au, Andrew
Published: (2026)

Tight Static Lower Bounds for Non-Adaptive Data Structures
by: Persiano, Giuseppe, et al.
Published: (2020)

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

Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
by: Cheng, Yu, et al.
Published: (2024)

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

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

Secretary, Prophet, and Stochastic Probing via Big-Decisions-First
by: Rubinstein, Aviad, et al.
Published: (2026)

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)

Reconstructing Bounded Treelength Graphs with Linearithmic Shortest Path Distance Queries
by: Kaudan, Chirag, et al.
Published: (2026)

Tight Bounds on the Number of Closest Pairs in Vertical Slabs
by: Biniaz, Ahmad, et al.
Published: (2025)

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

One Attack to Rule Them All: Tight Quadratic Bounds for Adaptive Queries on Cardinality Sketches
by: Cohen, Edith, et al.
Published: (2024)

Lower Bound Techniques in the Comparison-Query Model and Inversion Minimization on Trees
by: Hu, Ivan, et al.
Published: (2022)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Tight (S)ETH-based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-Machine Scheduling
by: Bringmann, Karl, et al.
Published: (2026)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
by: Trabelsi, Ohad
Published: (2023)