Buchumschlag

Nearly Tight Bounds on Testing of Metric Properties

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bao, Yiqiao, Kannan, Sampath, Waingarten, Erik
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Discrete Mathematics Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Tight Bounds for Sparsifying Random CSPs
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

A Tight Bound on Localization of Electrical Flows
von: Gurel-Gurevich, Ori, et al.
Veröffentlicht: (2026)

Tight Paths and Tight Pairs in Weighted Directed Graphs
von: Balcázar, José Luis
Veröffentlicht: (2025)

Tight Localizations of Feedback Sets
von: Hecht, Michael, et al.
Veröffentlicht: (2020)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
von: Chakraborty, Dipayan, et al.
Veröffentlicht: (2024)

Near-Optimal Constructive Bounds for $\ell_2$ Prefix Discrepancy and Steinitz Problems via Affine Spectral Independence
von: Dutta, Kunal, et al.
Veröffentlicht: (2026)

Hop-Constrained Metric Embeddings and their Applications
von: Filtser, Arnold
Veröffentlicht: (2021)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
von: Chakrabarty, Deeparnab, et al.
Veröffentlicht: (2025)

Cutwidth Bounds via Vertex Partitions
von: Amarilli, Antoine, et al.
Veröffentlicht: (2025)

Temporal Graph Realization With Bounded Stretch
von: Mertzios, George B., et al.
Veröffentlicht: (2025)

Optimal Padded Decomposition For Bounded Treewidth Graphs
von: Filtser, Arnold, et al.
Veröffentlicht: (2024)

Testing Quasiperiodicity
von: Awofeso, Christine, et al.
Veröffentlicht: (2025)

A Nearly Optimal Deterministic Algorithm for Online Transportation Problem
von: Harada, Tsubasa, et al.
Veröffentlicht: (2024)

Near-linear time subhypergraph counting in bounded degeneracy hypergraphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2025)

Bounding $\varepsilon$-scatter dimension via metric sparsity
von: Bourneuf, Romain, et al.
Veröffentlicht: (2024)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs
von: Abbasi, Ali, et al.
Veröffentlicht: (2026)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
von: Swamy, Chaitanya, et al.
Veröffentlicht: (2025)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
von: Gaikwad, Ajinkya
Veröffentlicht: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
von: Klimm, Max, et al.
Veröffentlicht: (2022)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
von: Bentert, Matthias, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
von: Paul-Pena, Daniel, et al.
Veröffentlicht: (2022)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
von: German, Samuel
Veröffentlicht: (2026)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
von: Harada, Tsubasa
Veröffentlicht: (2024)

Bow Metrics and Hyperbolicity
von: Dragan, Feodor F., et al.
Veröffentlicht: (2024)

An $Ω(n \log n)$ Randomized Lower Bound for Cutting a Cake into Proportionally Fair Pieces
von: Arndt, Stephen, et al.
Veröffentlicht: (2026)

The Complexity of Diameter on H-free graphs
von: Oostveen, Jelle J., et al.
Veröffentlicht: (2024)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
von: de Montgolfier, Fabien, et al.
Veröffentlicht: (2025)

Distribution Testing in the Presence of Arbitrarily Dominant Noise with Verification Queries
von: Black, Hadley, et al.
Veröffentlicht: (2025)

Tight Inapproximability of Target Set Reconfiguration
von: Ohsaka, Naoto
Veröffentlicht: (2024)

$α_i$-Metric Graphs: Hyperbolicity
von: Dragan, Feodor F., et al.
Veröffentlicht: (2024)

On Tight Robust Coresets for $k$-Medians Clustering
von: Huang, Lingxiao, et al.
Veröffentlicht: (2025)

An Alternate Proof of Near-Optimal Light Spanners
von: Bodwin, Greg
Veröffentlicht: (2023)

An Improved Bound for the Beck-Fiala Conjecture
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

Bounding Width on Graph Classes of Constant Diameter
von: Dabrowski, Konrad K., et al.
Veröffentlicht: (2025)

Circulant TSP: Vertices of the Edge-Length Polytope and Superpolynomial Lower Bounds
von: Gutekunst, Samuel C.
Veröffentlicht: (2025)

Isomorphism Testing Parameterized by Genus and Beyond
von: Neuen, Daniel
Veröffentlicht: (2021)

Distortion of Metric Voting with Bounded Randomness
von: Cai, Ziyi, et al.
Veröffentlicht: (2026)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
von: Arkhipov, Pavel, et al.
Veröffentlicht: (2024)

Colouring Probe $H$-Free Graphs
von: Paulusma, Daniël, et al.
Veröffentlicht: (2025)