Imagen de Portada

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Cai, Jin-Yi, Maran, Ashwin, Young, Ben
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
por: Cai, Jin-Yi, et al.
Publicado: (2024)

Holant* Dichotomy on Domain Size 3: A Geometric Perspective
por: Cai, Jin-Yi, et al.
Publicado: (2025)

New Planar Algorithms and a Full Complexity Classification of the Eight-Vertex Model
por: Fan, Austen, et al.
Publicado: (2026)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
por: Komarath, Balagopal, et al.
Publicado: (2025)

A Dichotomy for Maximum PCSPs on Graphs
por: Nakajima, Tamio-Vesa, et al.
Publicado: (2024)

Reconfiguring Graph Homomorphisms on the Sphere
por: Lee, Jae-Baek, et al.
Publicado: (2018)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
por: Meng, Boning, et al.
Publicado: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
por: Eagling-Vose, Tala, et al.
Publicado: (2024)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
por: Bai, Tian, et al.
Publicado: (2026)

Complexity Aspects of Homomorphisms of Ordered Graphs
por: Čertík, Michal, et al.
Publicado: (2025)

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
por: MIT Hardness Group, et al.
Publicado: (2026)

A Dichotomy for Finite Abstract Simplicial Complexes
por: Meyer, Sebastian
Publicado: (2024)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
por: Baril, Ambroise, et al.
Publicado: (2024)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
por: Hörsch, Florian, et al.
Publicado: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
por: Dawar, Anuj, et al.
Publicado: (2025)

Graph Homomorphisms and Universal Algebra
por: Bodirsky, Manuel
Publicado: (2026)

Complexity Dichotomies for Graph Homomorphism Problems on Restricted Classes
por: SÉRGIO DE ANDRADE, PAULO
Publicado: (2025)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
por: Dvořák, Pavel, et al.
Publicado: (2022)

Dynamic Planar Graph Isomorphism is in DynFO
por: Datta, Samir, et al.
Publicado: (2026)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
por: MIT Hardness Group, et al.
Publicado: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
por: Abboud, Amir, et al.
Publicado: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
por: Fei, Yumou, et al.
Publicado: (2025)

Geometry Matters in Planar Storyplans
por: Dobler, Alexander, et al.
Publicado: (2025)

Proper vs Improper Quantum PAC learning
por: Nayak, Ashwin, et al.
Publicado: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
por: Roberson, David E., et al.
Publicado: (2023)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
por: Shih, Yu-Sheng, et al.
Publicado: (2026)

Recognizing 2-Layer and Outer $k$-Planar Graphs
por: Kobayashi, Yasuaki, et al.
Publicado: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
por: Bhargav, C. S., et al.
Publicado: (2025)

Linear Planar 3-SAT and Its Applications in Planning
por: Desbois, Victorien, et al.
Publicado: (2025)

A simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operations
por: Zhuk, Dmitriy
Publicado: (2024)

The Parameterized Complexity of Geometric 1-Planarity
por: Firbas, Alexander
Publicado: (2026)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
por: Zhuk, Dmitriy
Publicado: (2024)

Recovery Reductions, Conjectures, and Barriers
por: Nareddy, Tejas, et al.
Publicado: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
por: Ciardo, Lorenzo, et al.
Publicado: (2023)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
por: Hamm, Thekla, et al.
Publicado: (2026)

A General Framework for Low Soundness Homomorphism Testing
por: Mittal, Tushant, et al.
Publicado: (2025)

Lower Bounds for Learning Quantum States with Single-Copy Measurements
por: Lowe, Angus, et al.
Publicado: (2022)

A Complexity Dichotomy for Semilinear Target Sets in Automata with One Counter
por: Shakiba, Yousef, et al.
Publicado: (2025)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
por: Seppelt, Tim
Publicado: (2024)

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
por: Majumdar, Angshul
Publicado: (2026)