Copertina

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Wulf, Lasse
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Computational Geometry 52-08, 52B05, 68Q25 F.2.2; F.1.3
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

NP-hardness of p-adic linear regression
di: Baker, Gregory D.
Pubblicazione: (2026)

Maximum Solow--Polasky Diversity Subset Selection Is NP-hard Even in the Euclidean Plane
di: Emmerich, Michael T. M., et al.
Pubblicazione: (2026)

Complexities of Well-Quasi-Ordered Substructural Logics
di: Galatos, Nikolaos, et al.
Pubblicazione: (2025)

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

Finding Cliques in Geometric Intersection Graphs with Grounded or Stabbed Constraints
di: Keil, J. Mark, et al.
Pubblicazione: (2025)

The Word Problem for Products of Symmetric Groups
di: Simon, Hans U.
Pubblicazione: (2025)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
di: Xia, Mingji
Pubblicazione: (2026)

A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
di: Bodirsky, Manuel, et al.
Pubblicazione: (2024)

NP-hard problems are not in BQP
di: Czerwinski, Reiner
Pubblicazione: (2023)

Evolomino is NP-complete
di: Nikolaev, Andrei V.
Pubblicazione: (2025)

The Maximum Clique Problem in a Disk Graph Made Easy
di: Keil, J. Mark, et al.
Pubblicazione: (2024)

Eight-Partitioning Points in 3D, and Efficiently Too
di: Aronov, Boris, et al.
Pubblicazione: (2024)

NP-Completeness Proofs of All or Nothing, Water Walk, and Remembered Length Using the T-Metacell Framework
di: Eua-anant, Pakapim, et al.
Pubblicazione: (2025)

Parallel Algorithms for Group Isomorphism via Code Equivalence
di: Levet, Michael
Pubblicazione: (2026)

Flexible realizations existence: NP-completeness on sparse graphs and algorithms
di: Laštovička, Petr, et al.
Pubblicazione: (2024)

Robust Bichromatic Classification using Two Lines
di: Glazenburg, Erwin, et al.
Pubblicazione: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
di: Kelley, Zander, et al.
Pubblicazione: (2023)

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

Selecting a Maximum Solow-Polasky Diversity Subset in General Metric Spaces Is NP-hard
di: Emmerich, Michael T. M., et al.
Pubblicazione: (2026)

On the Complexity of Minimum Riesz s-Energy Subset Selection in Euclidean and Ultrametric Spaces
di: Emmerich, Michael T. M., et al.
Pubblicazione: (2026)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
di: Grochow, Joshua A., et al.
Pubblicazione: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
di: Hakoniemi, Tuomas, et al.
Pubblicazione: (2024)

Quantum algorithms through graph composition
di: Cornelissen, Arjan
Pubblicazione: (2025)

Quantum walks through generalized graph composition
di: Cornelissen, Arjan
Pubblicazione: (2025)

Maximum Matchings in Geometric Intersection Graphs
di: Bonnet, Édouard, et al.
Pubblicazione: (2019)

Induced Disjoint Paths Without an Induced Minor
di: Aboulker, Pierre, et al.
Pubblicazione: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
di: Edwards, Darren J.
Pubblicazione: (2025)

The Gallai Vertex Problem is $Θ_2^p$-Complete
di: Nikabadi, Amir, et al.
Pubblicazione: (2026)

The Complexity of Resilience Problems via Valued Constraint Satisfaction
di: Bodirsky, Manuel, et al.
Pubblicazione: (2023)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
di: Philip, Geevarghese, et al.
Pubblicazione: (2026)

Hamiltonian Quasigeodesics yield Nets
di: O'Rourke, Joseph
Pubblicazione: (2022)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
di: Lela, Marko
Pubblicazione: (2025)

Complexity Classification Transfer for CSPs via Algebraic Products
di: Bodirsky, Manuel, et al.
Pubblicazione: (2022)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
di: Lela, Marko
Pubblicazione: (2025)

Skeletal Cut Loci on Convex Polyhedra
di: O'Rourke, Joseph, et al.
Pubblicazione: (2023)

Prismatoid Band-Unfolding Revisited
di: O'Rourke, Joseph
Pubblicazione: (2026)

Quoridor is PSPACE-Complete
di: Drop, Marius, et al.
Pubblicazione: (2026)

Optimally Covering Large Triangles with Homothetic Unit Triangles
di: Boyer, John M.
Pubblicazione: (2026)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
di: Conneryd, Jonas, et al.
Pubblicazione: (2025)

On Small-depth Frege Proofs for PHP
di: Håstad, Johan
Pubblicazione: (2024)