Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.03685 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Similar Items
Paintbucket on graphs is PSPACE-complete
by: Saunders, Ethan J., et al.
Published: (2024)
by: Saunders, Ethan J., et al.
Published: (2024)
Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)
by: Ilmavirta, Joonas, et al.
Published: (2023)
The antiferromagnetic Ising model beyond line graphs
by: Jerrum, Mark
Published: (2026)
by: Jerrum, Mark
Published: (2026)
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)
by: Ahn, Jungho, et al.
Published: (2022)
Barriers for recent methods in geodesic optimization
by: Franks, Cole, et al.
Published: (2021)
by: Franks, Cole, et al.
Published: (2021)
On balanceable and simply balanceable regular graphs
by: Ahanjideh, Milad, et al.
Published: (2024)
by: Ahanjideh, Milad, et al.
Published: (2024)
P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)
by: Delgado, Daniel Cardona
Published: (2023)
Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)
by: Andel, Daniël, et al.
Published: (2025)
Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
by: Pak, Igor, et al.
Published: (2025)
by: Pak, Igor, et al.
Published: (2025)
Vanishing of Schubert coefficients in probabilistic polynomial time
by: Pak, Igor, et al.
Published: (2025)
by: Pak, Igor, et al.
Published: (2025)
The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)
by: Lin, Tianrong
Published: (2021)
Hive-type polytopes for quiver multiplicities and the membership problem for quiver moment cones
by: Chindris, Calin, et al.
Published: (2022)
by: Chindris, Calin, et al.
Published: (2022)
Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
by: Chan, Swee Hong, et al.
Published: (2023)
by: Chan, Swee Hong, et al.
Published: (2023)
Computational complexity of counting coincidences
by: Chan, Swee Hong, et al.
Published: (2023)
by: Chan, Swee Hong, et al.
Published: (2023)
Undecidability of Tiling the Plane with a Set of 5 Polyominoes
by: Kim, Yoonhu
Published: (2025)
by: Kim, Yoonhu
Published: (2025)
Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)
by: Harvey, David, et al.
Published: (2025)
Undecidability of Translational Tiling with 2 Polycubes
by: Kim, Yoonhu
Published: (2025)
by: Kim, Yoonhu
Published: (2025)
Tight complexity bounds for diagram commutativity verification
by: Malko, Artem, et al.
Published: (2025)
by: Malko, Artem, et al.
Published: (2025)
Symmetrization maps and minimal border rank Comon's conjecture
by: Mańdziuk, Tomasz, et al.
Published: (2024)
by: Mańdziuk, Tomasz, et al.
Published: (2024)
Box complexes: at the crossroad of graph theory and topology
by: Daneshpajouh, Hamid Reza, et al.
Published: (2023)
by: Daneshpajouh, Hamid Reza, et al.
Published: (2023)
The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)
by: Milanič, Martin, et al.
Published: (2023)
On 3-colorability of (claw, diamond)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2026)
by: Hodur, Nadzieja, et al.
Published: (2026)
A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)
by: Abdullah, Duaa, et al.
Published: (2025)
Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models
by: Gayral, Léo, et al.
Published: (2023)
by: Gayral, Léo, et al.
Published: (2023)
Results on three problems on isolation of graphs
by: Borg, Peter, et al.
Published: (2026)
by: Borg, Peter, 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)
by: Marković, Petar, et al.
Published: (2026)
Vanishing of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)
by: Pak, Igor, et al.
Published: (2024)
Positivity of Schubert Coefficients
by: Pak, Igor, et al.
Published: (2024)
by: Pak, Igor, et al.
Published: (2024)
Linear extensions of finite posets
by: Chan, Swee Hong, et al.
Published: (2023)
by: Chan, Swee Hong, et al.
Published: (2023)
On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs
by: Štorgel, Kenny Bešter, et al.
Published: (2025)
by: Štorgel, Kenny Bešter, et al.
Published: (2025)
Atropos-k is PSPACE-complete
by: Yang, Chao, et al.
Published: (2024)
by: Yang, Chao, et al.
Published: (2024)
Dominic Welsh: his work and influence
by: Farr, Graham, et al.
Published: (2024)
by: Farr, Graham, et al.
Published: (2024)
Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)
by: Dorochko, Leonid, et al.
Published: (2026)
Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)
by: Reddy, Sangam Balchandar, et al.
Published: (2024)
On the Complexity of Bipartite Degree Realizability
by: Miklós, István
Published: (2025)
by: Miklós, István
Published: (2025)
Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
by: Goldberg, Guy, et al.
Published: (2025)
by: Goldberg, Guy, et al.
Published: (2025)
The n-vehicle exploration problem is NP-complete
by: Cui, Jinchuan, et al.
Published: (2023)
by: Cui, Jinchuan, et al.
Published: (2023)
How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)
by: Fortnow, Lance
Published: (2026)
Graph polynomials: some questions on the edge
by: Farr, Graham, et al.
Published: (2024)
by: Farr, Graham, et al.
Published: (2024)
Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
by: Ye, Yuhan
Published: (2026)
by: Ye, Yuhan
Published: (2026)