:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autores principales:	Yang, Chao, Zhang, Zhujun
Formato:	Preprint
Publicado:	2024
Materias:	Combinatorics Computational Complexity 05C40 (Primary), 68Q17 (Secondary)
Acceso en línea:	https://arxiv.org/abs/2402.03685
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Paintbucket on graphs is PSPACE-complete
por: Saunders, Ethan J., et al.
Publicado: (2024)

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

The antiferromagnetic Ising model beyond line graphs
por: Jerrum, Mark
Publicado: (2026)

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

Barriers for recent methods in geodesic optimization
por: Franks, Cole, et al.
Publicado: (2021)

On balanceable and simply balanceable regular graphs
por: Ahanjideh, Milad, et al.
Publicado: (2024)

P not equal to NP
por: Delgado, Daniel Cardona
Publicado: (2023)

Hive is PSPACE-Hard
por: Andel, Daniël, et al.
Publicado: (2025)

Vanishing of Schubert coefficients is in ${\sf AM}\cap {\sf coAM}$ assuming the GRH
por: Pak, Igor, et al.
Publicado: (2025)

Vanishing of Schubert coefficients in probabilistic polynomial time
por: Pak, Igor, et al.
Publicado: (2025)

The Separation of $NP$ and $PSPACE$
por: Lin, Tianrong
Publicado: (2021)

Hive-type polytopes for quiver multiplicities and the membership problem for quiver moment cones
por: Chindris, Calin, et al.
Publicado: (2022)

Equality cases of the Alexandrov--Fenchel inequality are not in the polynomial hierarchy
por: Chan, Swee Hong, et al.
Publicado: (2023)

Computational complexity of counting coincidences
por: Chan, Swee Hong, et al.
Publicado: (2023)

Undecidability of Tiling the Plane with a Set of 5 Polyominoes
por: Kim, Yoonhu
Publicado: (2025)

Integer multiplication is at least as hard as matrix transposition
por: Harvey, David, et al.
Publicado: (2025)

Undecidability of Translational Tiling with 2 Polycubes
por: Kim, Yoonhu
Publicado: (2025)

Tight complexity bounds for diagram commutativity verification
por: Malko, Artem, et al.
Publicado: (2025)

Symmetrization maps and minimal border rank Comon's conjecture
por: Mańdziuk, Tomasz, et al.
Publicado: (2024)

Box complexes: at the crossroad of graph theory and topology
por: Daneshpajouh, Hamid Reza, et al.
Publicado: (2023)

The Upper Clique Transversal Problem
por: Milanič, Martin, et al.
Publicado: (2023)

On 3-colorability of (claw, diamond)-free graphs
por: Hodur, Nadzieja, et al.
Publicado: (2026)

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

Characterisation of the Set of Ground States of Uniformly Chaotic Finite-Range Lattice Models
por: Gayral, Léo, et al.
Publicado: (2023)

Results on three problems on isolation of graphs
por: Borg, Peter, et al.
Publicado: (2026)

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

Vanishing of Schubert Coefficients
por: Pak, Igor, et al.
Publicado: (2024)

Positivity of Schubert Coefficients
por: Pak, Igor, et al.
Publicado: (2024)

Linear extensions of finite posets
por: Chan, Swee Hong, et al.
Publicado: (2023)

On $\{k\}$-Roman graphs: complexity of recognition and the case of split graphs
por: Štorgel, Kenny Bešter, et al.
Publicado: (2025)

Atropos-k is PSPACE-complete
por: Yang, Chao, et al.
Publicado: (2024)

Dominic Welsh: his work and influence
por: Farr, Graham, et al.
Publicado: (2024)

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

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

On the Complexity of Bipartite Degree Realizability
por: Miklós, István
Publicado: (2025)

Nearly Tight Lower Bounds for Relaxed Locally Decodable Codes via Robust Daisies
por: Goldberg, Guy, et al.
Publicado: (2025)

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

How Does Machine Learning Manage Complexity?
por: Fortnow, Lance
Publicado: (2026)

Graph polynomials: some questions on the edge
por: Farr, Graham, et al.
Publicado: (2024)

Parameterized Complexity of Stationarity Testing for Piecewise-Affine Functions and Shallow CNN Losses
por: Ye, Yuhan
Publicado: (2026)