:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Meijer, Lucas, Miltzow, Till, Ockenfels, Johanna, Stojaković, Miloš
Format:	Preprint
Published:	2026
Subjects:	Computational Geometry 68Q17
Online Access:	https://arxiv.org/abs/2604.26749
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

How Hard is it to be a Star? Convex Geometry and the Real Hierarchy
by: Schaefer, Marcus, et al.
Published: (2025)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Recognizing Penny and Marble Graphs is Hard for Existential Theory of the Reals
by: Lubiw, Anna, et al.
Published: (2025)

Recent Advances in Debordering Methods
by: Dutta, Pranjal, et al.
Published: (2025)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Minimal Unimodal Decomposition is NP-Hard on Graphs
by: K, Mishal Assif P, et al.
Published: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Quantum Speedup for Some Geometric 3SUM-Hard Problems and Beyond
by: Keil, J. Mark, et al.
Published: (2024)

A Unified FPT Framework for Crossing Number Problems
by: de Verdière, Éric Colin, et al.
Published: (2024)

On Equivalent Characterizations of NP in Abstract Models of Computation
by: Kirn, Jeremy C., et al.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Quantum Time-Space Tradeoffs for Matrix Problems
by: Beame, Paul, et al.
Published: (2024)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

Exact values of generic subrank
by: Pielasa, Paweł, et al.
Published: (2024)

Border subrank via a generalised Hilbert-Mumford criterion
by: Biaggi, Benjamin, et al.
Published: (2024)

Towards Single Exponential Time for Temporal and Spatial Reasoning: A Study via Redundancy and Dynamic Programming
by: Lagerkvist, Victor, et al.
Published: (2026)

The algorithmic Fried Potato Problem in two dimensions
by: Criado, Francisco, et al.
Published: (2025)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

The geometry and singularities of the Bilinear scheme
by: Obcowska, Weronika
Published: (2026)

Friends-and-strangers is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
by: Lin, Tianrong
Published: (2021)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)