Copertina

Non-Signaling Locality Lower Bounds for Dominating Set

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Fleming, Noah, Hopkins, Max, Yoshida, Yuichi
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

Sensitivity Lower Bounds for Approximaiton Algorithms
di: Fleming, Noah, et al.
Pubblicazione: (2024)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
di: Yoshida, Yuichi
Pubblicazione: (2026)

Lower Bounds for Dominating Set in Ball Graphs and for Weighted Dominating Set in Unit-Ball Graphs
di: de Berg, Mark, et al.
Pubblicazione: (2026)

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

Tolerant Testing for Unique Games
di: Yoshida, Yuichi
Pubblicazione: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
di: Yoshida, Yuichi
Pubblicazione: (2026)

Testing Monotonicity of Real-Valued Functions on DAGs
di: Yoshida, Yuichi
Pubblicazione: (2026)

Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
di: Funke, Daniel, et al.
Pubblicazione: (2024)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
di: Sakaue, Shinsaku, et al.
Pubblicazione: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
di: Hwang, Samuel, et al.
Pubblicazione: (2024)

Average sensitivity of the Knapsack Problem
di: Kumabe, Soh, et al.
Pubblicazione: (2024)

Lipschitz Continuous Algorithms for Covering Problems
di: Kumabe, Soh, et al.
Pubblicazione: (2023)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
di: Kothari, Pravesh, et al.
Pubblicazione: (2024)

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

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

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
di: Soma, Tasuku, et al.
Pubblicazione: (2025)

Courcelle's Theorem for Lipschitz Continuity
di: Gima, Tatsuya, et al.
Pubblicazione: (2025)

Exact Optimization for Minimum Dominating Sets
di: Zhu, Enqiang, et al.
Pubblicazione: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
di: Singer, Noah G., et al.
Pubblicazione: (2026)

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

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
di: Saito, Rin, et al.
Pubblicazione: (2025)

Dominating Set with Quotas: Balancing Coverage and Constraints
di: Chatterjee, Sobyasachi, et al.
Pubblicazione: (2026)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
di: Singh, Sipra
Pubblicazione: (2025)

Revisiting a Successful Reduction Rule for Dominating Set
di: Geis, Lukas, et al.
Pubblicazione: (2025)

Structural Parameterization of Locating-Dominating Set and Test Cover
di: Chakraborty, Dipayan, et al.
Pubblicazione: (2024)

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

Lower Bounds for Greedy Teaching Set Constructions
di: Compton, Spencer, et al.
Pubblicazione: (2025)

Analysis of a Random Local Search Algorithm for Dominating Set
di: Higl, Hendrik
Pubblicazione: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
di: Yoshida, Yuichi, et al.
Pubblicazione: (2025)

Lower Bounds on Flow Sparsifiers with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2026)

New Algorithms and Lower Bounds for Streaming Tournaments
di: Ghosh, Prantar, et al.
Pubblicazione: (2024)

Lower Bounds on $0$-Extension with Steiner Nodes
di: Chen, Yu, et al.
Pubblicazione: (2024)

Double Exponential Lower Bound for Telephone Broadcast
di: Tale, Prafullkumar
Pubblicazione: (2024)

Dynamic PageRank: Algorithms and Lower Bounds
di: Jayaram, Rajesh, et al.
Pubblicazione: (2024)

Fine Grained Lower Bounds for Multidimensional Knapsack
di: Doron-Arad, Ilan, et al.
Pubblicazione: (2024)

Faster MAX-CUT on Bounded Threshold Rank Graphs
di: Anderson, Prashanti, et al.
Pubblicazione: (2025)

Improved Dominance Filtering for Unions and Minkowski Sums of Pareto Sets
di: Karathanasis, Konstantinos, et al.
Pubblicazione: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
di: Solomon, Shay, et al.
Pubblicazione: (2023)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
di: Adar, Tomer, et al.
Pubblicazione: (2026)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
di: Focke, Jacob, et al.
Pubblicazione: (2022)