Copertina

Sublinear-Time Lower Bounds for Approximating Matching Size using Non-Adaptive Queries

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Shah, Vihan
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

New Lower Bounds in Merlin-Arthur Communication and Graph Streaming Verification
di: Ghosh, Prantar, et al.
Pubblicazione: (2024)

Dynamic $(1+ε)$-Approximate Matching Size in Truly Sublinear Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2023)

An Improved Fully Dynamic Algorithm for Counting 4-Cycles in General Graphs using Fast Matrix Multiplication
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

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

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

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
di: Bille, Philip, et al.
Pubblicazione: (2022)

Arboricity and Random Edge Queries Matter for Triangle Counting using Sublinear Queries
di: Bishnu, Arijit, et al.
Pubblicazione: (2025)

Deterministic Dynamic Maximal Matching in Sublinear Update Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

Approximate Butterfly Counting in Sublinear Time
di: Luo, Chi, et al.
Pubblicazione: (2026)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
di: Dai, Jiangqi, et al.
Pubblicazione: (2025)

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

Breaking Barriers: Combinatorial Algorithms for Non-monotone Submodular Maximization with Sublinear Adaptivity and $1/e$ Approximation
di: Chen, Yixin, et al.
Pubblicazione: (2025)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

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

Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds
di: Kapralov, Michael, et al.
Pubblicazione: (2022)

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

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

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

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
di: Chen, Xi, et al.
Pubblicazione: (2024)

Sublinear Time Low-Rank Approximation of Hankel Matrices
di: Kapralov, Michael, et al.
Pubblicazione: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
di: Musco, Cameron, et al.
Pubblicazione: (2024)

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

Computing String Covers in Sublinear Time
di: Radoszewski, Jakub, et al.
Pubblicazione: (2024)

On Solving Linear Systems in Sublinear Time
di: Andoni, Alexandr, et al.
Pubblicazione: (2018)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
di: Chitnis, Rajesh, et al.
Pubblicazione: (2024)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time
di: Braverman, Vladimir, et al.
Pubblicazione: (2024)

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

Solving the Correlation Cluster LP in Sublinear Time
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Counting Distinct Square Substrings in Sublinear Time
di: Charalampopoulos, Panagiotis, et al.
Pubblicazione: (2025)

Non-Signaling Locality Lower Bounds for Dominating Set
di: Fleming, Noah, et al.
Pubblicazione: (2026)

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

Fully Dynamic Exact Edge Connectivity in Sublinear Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2023)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
di: Kempa, Dominik, et al.
Pubblicazione: (2024)

Learning-augmented Maximum Independent Set
di: Braverman, Vladimir, et al.
Pubblicazione: (2024)

Sublinear Time Quantum Algorithm for Attention Approximation
di: Song, Zhao, et al.
Pubblicazione: (2026)

Approximate Graph Propagation Revisited: Dynamic Parameterized Queries, Tighter Bounds and Dynamic Updates
di: Zhao, Zhuowei, et al.
Pubblicazione: (2025)

Statistical Query Lower Bounds for Smoothed Agnostic Learning
di: Diakonikolas, Ilias, et al.
Pubblicazione: (2026)

Minimizing Makespan in Sublinear Time via Weighted Random Sampling
di: Fu, Bin, et al.
Pubblicazione: (2026)

On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time
di: Kwok, Tsz Chiu, et al.
Pubblicazione: (2025)