:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Dorfer, Joseph
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2602.09573
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

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

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

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

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

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

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

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

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

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

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

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

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

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

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

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

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

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

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

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

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

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

Forrelation is Extremally Hard
by: Girish, Uma, et al.
Published: (2025)

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

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