Cover Image

The Complexity Classes of Hamming Distance Recoverable Robust Problems

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Grüne, Christoph
Format:	Preprint
Published:	2022
Subjects:	Computational Complexity Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On the Complexity of Recoverable Robust Optimization in the Polynomial Hierarchy
by: Grüne, Christoph, et al.
Published: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
by: Grüne, Christoph, et al.
Published: (2026)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

The Complexity of Stackelberg Pricing Games
by: Grüne, Christoph, et al.
Published: (2025)

Random Reed-Solomon Codes are List Recoverable with Optimal List Size
by: Doron, Dean, et al.
Published: (2024)

Continuous Defensive Domination Problems
by: Grüne, Christoph, et al.
Published: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

Computational Complexity of the Recoverable Robust Shortest Path Problem with Discrete Recourse
by: Jackiewicz, Marcel, et al.
Published: (2024)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Monotone Circuit Complexity of Matching
by: Cavalar, Bruno, et al.
Published: (2025)

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

A Note on the Complexity of Directed Clique
by: Gutowski, Grzegorz, et al.
Published: (2026)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)

Completeness in the Polynomial Hierarchy for many natural Problems in Bilevel and Robust Optimization
by: Grüne, Christoph, et al.
Published: (2023)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
by: Fiorini, Eugene, et al.
Published: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
by: Mu, Ta-Yu, et al.
Published: (2024)

A Compendium of Reductions: reductions.network
by: Grüne, Christoph, et al.
Published: (2025)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Complexity Aspects of Homomorphisms of Ordered Graphs
by: Čertík, Michal, et al.
Published: (2025)

On the Parameterized Complexity of Grundy Domination and Zero Forcing Problems
by: Scheffler, Robert
Published: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Structural Origins of Cubic Complexity in Pebble Motion
by: Nakamigawa, Tomoki, et al.
Published: (2025)

The Complexity of Blocking All Solutions
by: Grüne, Christoph, et al.
Published: (2025)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
by: Aravind, Abhiram, et al.
Published: (2026)

Constant-Cost Communication is not Reducible to k-Hamming Distance
by: Fang, Yuting, et al.
Published: (2024)

Constant Rate Isometric Embeddings of Hamming Metric into Edit Metric
by: Bhattacharya, Sudatta, et al.
Published: (2025)

Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges
by: Bok, Jan, et al.
Published: (2021)

Complexity results for a cops and robber game on directed graphs
by: Ben-Ameur, Walid, et al.
Published: (2024)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
by: Nakajima, Tamio-Vesa, et al.
Published: (2025)

Computational Complexity of Swish
by: Horiyama, Takashi, et al.
Published: (2026)

Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
by: Le, Hoang-Oanh, et al.
Published: (2023)

Distance Vector Domination
by: Cordasco, Gennaro, et al.
Published: (2024)

The Complexity of Graph Exploration Games
by: Fuchs, Janosch, et al.
Published: (2023)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)