:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autor principal:	Dorfer, Joseph
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2602.09573
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
por: Dorfer, Joseph
Publicado: (2026)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
por: Guruswami, Venkatesan, et al.
Publicado: (2023)

Refuting Perfect Matchings in Spectral Expanders is Hard
por: Biswas, Ari, et al.
Publicado: (2025)

Three Hardness Results for Graph Similarity Problems
por: Sun, He, et al.
Publicado: (2023)

Improved Hardness Results for the Guided Local Hamiltonian Problem
por: Cade, Chris, et al.
Publicado: (2022)

New Hardness Results for Low-Rank Matrix Completion
por: Chawin, Dror, et al.
Publicado: (2025)

Hardness Results on Characteristics for Elastic-Degenerated Strings
por: Köppl, Dominik, et al.
Publicado: (2024)

Hardness and Algorithmic Results for Roman \{3\}-Domination
por: Reddy, Sangam Balchandar
Publicado: (2025)

Phase Transitions in Decision Problems Over Odd-Sized Alphabets
por: Jackson, Andrew
Publicado: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
por: Tiegel, Stefan
Publicado: (2024)

Improved Hardness Results for Min-Max Optimization with Coupled Constraints
por: Bernasconi, Martino, et al.
Publicado: (2024)

On the Parameterized Complexity of Odd Coloring
por: Bhyravarapu, Sriram, et al.
Publicado: (2025)

When and Why is Persuasion Hard? A Computational Complexity Result
por: Wojtowicz, Zachary
Publicado: (2024)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
por: Balliu, Alkida, et al.
Publicado: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
por: Gaikwad, Ajinkya, et al.
Publicado: (2025)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
por: Basu, Arpon, et al.
Publicado: (2024)

Hardness of Regular Expression Matching with Extensions
por: Nogami, Taisei, et al.
Publicado: (2026)

New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs
por: Brakensiek, Joshua, et al.
Publicado: (2026)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
por: Chavrimootoo, Michael C., et al.
Publicado: (2026)

Hardness of SetCover Reoptimization
por: Jansen, Klaus, et al.
Publicado: (2025)

On the Hardness of the Drone Delivery Problem
por: Bartlmae, Simon, et al.
Publicado: (2025)

Bounds for Hardness Condensation in the Query Model
por: Kayal, Chandrima, et al.
Publicado: (2026)

Hardness of clique approximation for monotone circuits
por: Błasiok, Jarosław, et al.
Publicado: (2025)

Hardness Amplification via Group Theory
por: Nareddy, Tejas, et al.
Publicado: (2024)

Hard-to-Sample Distributions from Robust Extractors
por: Byramji, Farzan, et al.
Publicado: (2026)

Tetris is Hard with Just One Piece Type
por: MIT Hardness Group, et al.
Publicado: (2026)

Hard CNF Instances for Ideal Proof Systems
por: Hakoniemi, Tuomas, et al.
Publicado: (2026)

Are Depth-2 Regular Expressions Hard to Intersect?
por: Ascone, Rocco, et al.
Publicado: (2025)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
por: Ramya, C., et al.
Publicado: (2025)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
por: Casteigts, Arnaud, et al.
Publicado: (2026)

New Techniques for Constructing Rare-Case Hard Functions
por: Nareddy, Tejas, et al.
Publicado: (2024)

Compression of Voxelized Vector Field Data by Boxes is Hard
por: Zhang, Simon
Publicado: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
por: Egidy, Fabian, et al.
Publicado: (2024)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
por: Chew, Leroy, et al.
Publicado: (2024)

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

On the Computational Hardness of Transformers
por: Saha, Barna, et al.
Publicado: (2026)

Forrelation is Extremally Hard
por: Girish, Uma, et al.
Publicado: (2025)

Finding Minimum Matching Cuts in $H$-free Graphs
por: Lucke, Felicia, et al.
Publicado: (2025)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
por: Fu, Cheng-Hao, et al.
Publicado: (2025)